Common Shortest Path Algorithms

• Dijkstra’s Algorithm
• Bellman Ford’s Algorithm
• Floyd Warshall’s Algorithm

Dijkstra’s Algorithm

The Dijkstra’s Algorithm is a greedy algorithm that is used to find the minimum distance between a node and all other nodes in a given graph. Here we can consider node as a router and graph as a network. It uses weight of edge .ie, distance between the nodes to find a minimum distance route.

Algorithm:

1: Mark the source node current distance as 0 and all others as infinity.

2: Set the node with the smallest current distance among the non-visited nodes as the current node.

3: For each neighbor, N, of the current node:

• Calculate the potential new distance by adding the current distance of the current node with the weight of the edge connecting the current node to N.
• If the potential new distance is smaller than the current distance of node N, update N’s current distance with the new distance.

4: Make the current node as visited node.

5: If we find any unvisited node, go to step 2 to find the next node which has the smallest current distance and continue this process.

Example:

Consider the graph G:

Now,we will start normalising graph one by one starting from node 0.

Nearest neighbour of 0 are 2 and 1 so we will normalize them first .

Similarly we will normalize other node considering it should not form a cycle and will keep track in visited nodes.

In between sending and receiving data packets from the sender to the receiver, it will go through many routers and subnets. So as a part of increasing the efficiency in routing the data packets and decreasing the traffic, we must find the shortest path. In this article, we are discussing the shortest path algorithms.