Shortest Path Algorithms¶

Single Source Shortest Path Algorithms¶

Single source shortest path algorithms are essential techniques in graph theory and computer science used to find the shortest path from a single source vertex to all other vertices in a weighted graph. They have widespread applications in various domains, such as network routing, GPS navigation, and optimization problems.

Single source to find the shortest path from a single source vertex to all other vertices in a weighted graph
All pairs to find the shortest path between all pairs of vertices in a weighted graph
Applications
- Network routing
- GPS navigation
- Optimization problems

Dijkstra’s Algorithm¶

Dijkstra’s algorithm is a widely-used algorithm to find the shortest path from a single source vertex to all other vertices in a weighted graph. It works by iteratively selecting the vertex with the smallest tentative distance from the source and relaxing its neighboring vertices.

invented by Edsger Dijkstra
visualization https://visualgo.net/en/sssp

Pseudo-code for Dijkstra’s Algorithm¶

Dijkstra’s Algorithm¶

function dijkstra(graph, source):
  create a priority queue PQ
  initialize distances to all vertices as infinity
  set the distance to the source as 0
  enqueue source to PQ

  while PQ is not empty:
    current_vertex = vertex with the smallest distance in PQ
    remove current_vertex from PQ

    for each neighbor of current_vertex:
      edge_weight = weight of the edge between current_vertex and neighbor
      tentative_distance = distance to current_vertex + edge_weight
      if tentative_distance < distance to neighbor:
        set distance to neighbor as tentative_distance
        add neighbor to PQ