by Dinesh Thakur Category: Graphs

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

 Shortest Path Algorithm

About Dinesh Thakur

Dinesh ThakurDinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.

Search Content