Published on

Shortest path

Given a weighted graph and two vertices u and v, find a path of minimum total weight between u and v

applications:

  • internet packet routing
  • flight reservations
  • driving directions

single source on unweighted graph ⇒ just use BFS

Dijkstra algorithm

This algorithm constructs the shortest path tree from a source node. It does not allow negative edge weights and is similar to Prim's algorithm. The algorithm employs a greedy strategy and has a complexity of O(|E| + |V|log|V|). It is widely used in various applications, such as artificial satellite GPS software. Since negative edges do not usually exist in the real world, Dijkstra's algorithm is one of the most suitable algorithms for practical use.

  1. Set the starting node.
  2. Save the minimum cost of each node based on the starting node.
  3. Select the node with the lowest cost among the nodes that have not been visited.
  4. Consider the case of going to a specific node through the selected node and update the minimum cost.
  5. Repeat steps 3-4 until all nodes have been visited.

Bellman-ford algorithm

When all edge costs are positive, you can use Dijkstra's algorithm. However, if there are negative edges and negative cycles, a node with negative infinity occurs. In this case, you should use the Bellman-Ford algorithm. The Bellman-Ford algorithm can be used in situations involving negative edges and can detect negative cycles. The basic time complexity of the Bellman-Ford algorithm is O(VE), slower than Dijkstra's algorithm.

  1. Choose a starting node.
  2. Initialize the shortest distance table as infinite.
  3. Repeat the following process n-1 times: Check each of the total e edges one by one. Calculate the cost of going to other nodes through each edge and update the shortest distance table.
  4. If you want to check for the existence of a negative cycle, repeat step 3. once more. If the shortest distance table is updated this time, a negative cycle exists.
dijkstra_bellman_ford

Floyd-Warshall

Dijkstra's and Bellman-Ford algorithms are algorithms that find the shortest path from one vertex to another when starting from a single vertex. However, if you want to find the shortest paths between all pairs of vertices, you need to use the Floyd-Warshall algorithm. While Dijkstra's algorithm chooses the least cost one by one, the Floyd-Warshall algorithm performs the algorithm based on the intermediate vertex.

dijkstra_bellman_ford

The green zone is a changeable area. Nodes with self-loops and containing intermediate vertices are not able to be changed.

The key idea of the Floyd-Warshall algorithm is to find the shortest distance based on the intermediate vertex. Calculate the number of cases where all n nodes are passed through.

The time complexity is O(V^3).