What are Weighted Graphs?
A Graph is said to be Weighted if each edge is assigned a 'weight'. The weight of an
edge can denote distance, time, or anything that models the 'connection' between
the pair of vertices it connects.
TWO SHORTEST PATH ALGORITHMS
If there is a path from vertex u to vertex v in a network G, any path of minimum length from u to v is a
Shortest path (SP) from u to v. and its weight is the shortest distance (SD) from u to v.
Dijkstra's Algorithm
• Let G = (V, E), where V = {1, 2, . . . , n} is a directed network in which the weight of every arc i nonnegative. This
algorithm can be used to find the SP and SD from any fixed vertex (say vertex 1 ) to any vertex i if there is a
directed path from 1 to i. Let a(i, j) be the weight of the arc from i to j. If there is no arc from i to j, a(i, j) is +∞.
Each vertex i is assigned a label that is either permanent or tentative. The permanent label L(i) is the SD from 1
to i. The tentative label L′(i) is an upper bound of L(i). At each stage of the algorithm, P is the set of vertices with
permanent labels and T is the set of vertices with tentative labels. Initially, P is the set {1} with L(1) = 0 and L′(j)
= a(1, j) for all j.
• Djikstra used this property in the opposite direction i.e. we overestimate the distance of each vertex from the starting
vertex. Then we visit each node and its neighbors to find the shortest subpath to those neighbors.
• The algorithm uses a greedy approach in the sense that we find the next best solution hoping that the end result is the
best solution for the whole problem.
Example of Dijkstra's algorithm
It is easier to start with an example and then think about the algorithm.
Advantages and Disadvantages of Dijkstra's Algorithm
Let us discuss some advantages of Dijkstra's Algorithm:
1.One primary advantage of using Dijkstra's Algorithm is that it has an almost linear time and space complexity.
2.We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single
source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the
destination vertex.
3.This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-
negative.
Despite having multiple advantages, Dijkstra's algorithm has some disadvantages also, such as:
1.Dijkstra's Algorithm performs a concealed exploration that utilizes a lot of time during the process.
2.This algorithm is impotent to handle negative edges.
3.Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.
4.It also requires maintenance to keep a record of vertices that have been visited.
Dijkstra's Algorithm has various real-world applications, some
of which are stated below:
• Digital Mapping Services in Google Maps
• Social Networking Applications
• Telephone Network
• IP routing to find Open Shortest Path First
• Flight Program
