Dijkstra's algorithm is a popular algorithm used to find the shortest path between two nodes in a graph. It is often used in routing and navigation systems.

Overview

  • What is Dijkstra's Algorithm? Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights.

  • When to Use Dijkstra's Algorithm? You should use Dijkstra's algorithm when you need to find the shortest path from a single source to all other nodes in a graph with non-negative weights.

Algorithm Steps

  1. Initialize the algorithm

    • Create a set of unvisited nodes.
    • Assign a distance value to each node in the graph. Initialize all nodes as unvisited. The distance value for the starting node is 0, and for all other nodes, it is set to infinity.

  2. Select the unvisited node with the smallest distance

    • From the set of unvisited nodes, select the node with the smallest distance.

  3. Update the distances of neighboring nodes

    • For each neighboring node of the selected node, calculate the distance from the starting node to the neighboring node through the selected node.
    • If this distance is smaller than the previously recorded distance for the neighboring node, update the distance.

  4. Mark the selected node as visited

    • Once the selected node has been visited, mark it as visited and remove it from the set of unvisited nodes.

  5. Repeat steps 2-4 until all nodes have been visited

    • Continue selecting unvisited nodes with the smallest distance and updating the distances of neighboring nodes until all nodes have been visited.

  6. Output the shortest path

    • Once all nodes have been visited, the shortest path from the starting node to all other nodes has been found.

Example

Let's say we have a graph with the following nodes and distances:

A -- 2 -- B
|    |
5    1
|    |
C -- 3 -- D

To find the shortest path from A to D using Dijkstra's algorithm, we would follow these steps:

  1. Initialize the algorithm.
  2. Select A as the starting node.
  3. Update the distances of B and C.
  4. Select B as the next unvisited node.
  5. Update the distance of D.
  6. Select C as the next unvisited node.
  7. Update the distance of D.
  8. Select D as the next unvisited node.
  9. Mark D as visited.
  10. Output the shortest path from A to D: A -> B -> D with a distance of 3.

More Information

For more detailed information on Dijkstra's algorithm, you can read our comprehensive guide on Graph Algorithms.

Note: The image below shows an example of a graph where Dijkstra's algorithm can be applied.

Dijkstra Graph