Explain Shortest Path Algorithm.

Shortest path can be calculated only for the weighted graphs. The edges connecting two vertices can be assigned a nonnegative real number, called the weight of the edge. A graph with such weighted edges is called a weighted graph.

  Let G be a weighted graph. Let u and v be two vertices in G, and let P be a path in G from u to v. The weight of the path P is the sum of the weights of all the edges on the path P, which is also called the weight of v from u via P.

Let G be a weighted graph representing a highway structure. Suppose that the weight of an edge represents the travel time. For example, to plan monthly business trips, a salesperson wants to find the shortest path (that is, the path with the smallest weight) from her or his city to every other city in the graph. Many such problems exist in which we want to find the shortest path from a given vertex, called the source, to every other vertex in the graph. This section describes the shortest path algorithm, also called the greedy algorithm, developed by Dijkstra.

Shortest Path

Given a vertex, say vertex (that is, a source), this section describes the shortest path algorithm.

The general algorithm is:

1. Initialize the array smallestWeight so that smallestWeight[u] = weights[vertex, u].

2. Set smallestWeight[vertex] = 0.

3. Find the vertex, v, that is closest to vertex for which the shortest path has not been determined.

4. Mark v as the (next) vertex for which the smallest weight is found.

5. For each vertex w in G, such that the shortest path from vertex to w has not been determined and an edge (v, w) exists, if the weight of the path to w via v is smaller than its current weight, update the weight of w to the weight of v + the weight of the edge (v, w).

Because there are n vertices, repeat Steps 3 through 5, n – 1 times.

Example : Shortest Path