Data Structures and Algorithms - Old Questions
10. State MST (Minimum Cost Spanning Tree) problem and shortest path (single source and all other destination) problem. Name the algorithms for solving these problems.
MST (Minimum Cost Spanning Tree)
A
spanning tree is a subset of Graph G, which has all the vertices of G with
minimum possible number of edges. Hence, a spanning tree does not have cycles
and it cannot be disconnected.
In a
weighted graph, a minimum spanning tree (MST) is a spanning tree that
has minimum weight than all other spanning trees of the same graph.
There
are three different algorithms to construct the minimum spanning tree:
- Prim’s algorithm: Grows the tree
in stages. Selects an edge with lowest cost that can be added to the tree
without forming cycle.
- Kruskal’s algorithm: In each stage select the edge in non-decreasing order of cost.
- Sollin’s algorithm: Select several edges at each stage.
The
Shortest Path
Consider a weighted graph G. The
length of a path in a weighted graph is the sum of the weights of the edges of
this path and the shortest path between two vertices is the minimum length of
the path.
The Dijkstra’s Algorithm finds the shortest path between two vertices
in weighted graph.