Application of Graph – Shortest Path Problems

Determining the optimal path(such that the sum of weight of its constituent edges is minimum) between the nodes of a weighted graph is referred as Shortest Path Problems.

There could be many variants of shortest path problems, widely known are
1. Single source shortest path problem
2. All pair shortest path problem

1. Single source shortest path problem

The problem says given the vertex(say source), find the shortest path to the desired vertex. E.W. Dijkstra proposed the solution, known as Dijkstra’s algorithm. Interestingly, the algorithm does not only find the shortest path to the desired vertex, but to all the vertices. It follows the greedy approach.

Relaxing a node:

It refers to updating the optimal cost to all the adjacent nodes to a vertex v, provided the cost would be improved on including the path via v.
See the given graph,

The relaxing of a vertex is the primary structure of Dijkstra’s algorithm.
It says decide a source vertex S, through which, the shortest path to all the vertices (or to the desired vertex) is to be found. Two sets of vertices maintained one visited and unvisited. As the name justified, visited for a set of visited vertices and unvisited for a set of non-visited vertices. Relax the source S i.e. all the adjacent will be explored. At this point, S will be in the visited set and rest all will be in the unvisited set. Select a vertex from the unvisited set, causing the least cost as computed on relaxing. See below,

Relaxing to the vertices are applied based on which one is nearest(causes least or optimal cost). Every time a vertex is relaxed, it becomes visited. This’ll be repeated until all the vertices become visited. Continue the above graph,

At last, the number associated with each vertex represents the least cost from the source S to that node.

Pseudocode for Dijkstra Algorithm:

Say G(V, E) denotes a graph, S as a set containing the visited set of vertices, W an adjacency matrix(costs are there rather than 0’s and 1’s) of the graph G.

Dijkstra(G, W, S)
Initialize single source (G, S)
S = ?
Q = G.V //Q, priority Queue data structure
Until Q not Empty
    u = extract-min(Q)
    S = S U {u}
    for each vertex v ? G.adj(u)
        relax(u, v, W)

The running time of above algo is O(E*logV)
Note:-
Dijkstra’s algorithm fails if the graph contains negative weights with a cycle. In that case another algorithm, Bellman-Ford algorithm is preferred, which detects negative weight cycle and rejects it.

2. All pair shortest path problem

This refers to finding the optimal path between each pair of vertices.
We can not apply the Dijkstra’s algorithm here as it would take V * O(E*LogV). With a dense graph, it would become V³LogV.
The proposed solution is Floyd Warshall algorithm, that uses dynamic programming approach. This algorithm takes O(V³).

 Applications possesses Shortest Path Problems:

• Various Maps
• Robot navigation
• Mapping of Texture
• Typesetting in TeX
• Traffic planning
• Road Network
• Determining Optimal pipelining of VLSI chip
• Telemarketer operator scheduling
• Approximating piecewise linear functions
• Routing protocols (RIP, OSPF, BGP)
• Exploiting arbitrage opportunities in currency exchange

So that’s all for this tutorial. Hope this helps and you like the tutorial. Do ask for any queries in the comment box and provide your valuable feedback.
Do not forget to SHARE and SUBSCRIBE.
Keep Coding!! Happy Coding!! 🙂

Recommended -