Shortest Path in a Graph

External

• https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/ZAaJA/bfs-and-shortest-paths
• 5 Ways to Find the Shortest Path in a Graph https://betterprogramming.pub/5-ways-to-find-the-shortest-path-in-a-graph-88cfefd0030f

Internal

• Graphs
• Graph Search | Breadth-First Search

Overview

There are several algorithms that compute the shortest path between two vertices in a graph, and they can be used or not depending on the characteristics of the graph, such as whether is directed or undirected, the edges have weights, the weights are. negative or not.

Shortest Path Algorithms

• Breadth-First Search-based Shortest Path Algorithm

TODO

Reshape this page to accommodate Dijkstra's Algorithm.

Algorithm

The algorithm is (differences to the canonical BFS algorithm are emphasized):

BFS_with_Shortest_Path(graph G, start vertex s)
  # All nodes are assumed unexplored
  initialize a Queue Q (FIFO)
  mark s as explored
  annotate s with distance 0
  place s in Q
  while Q has elements
    remove the head of the queue v
    for each edge (v, w):
      if w unexplored:
        mark w as explored
        annotate w with a distance dist(w) = dist(v) + 1
        add w to Q

The distance computed on reachable node gives the "layer" and the distance from the start node s.