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
• Our Dijkstra Shortest Paths Visualizer
• visualgo.net

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