Shortest Path in a Graph: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(23 intermediate revisions by the same user not shown)
Line 4: Line 4:


=Internal=
=Internal=
* [[Graphs#Subjects|Graphs]]
* [[Graphs#Graph_Algorithms|Graphs]]
* [[Graph_Search#Breadth-First_Search_.28BFS.29|Graph Search | Breadth-First Search]]
* [[Graph_Search#Breadth-First_Search_.28BFS.29|Graph Search | Breadth-First Search]]
=TODO=
<font color=darkgray>Reshape this page to accommodate [[Dijkstra's Algorithm]].</font>


=Overview=
=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.


The BFS algorithm as described above can be used, with a very small constant-time addition, to keep track of the layer each newly discovered node is in, relative to the start node, and that will automatically indicate the shortest path between the start node s and a reachable node v. It works by annotating the start vertex with 0 and then annotating each new node with  D + 1, where D is the distance of the node we discovered the new node from.
=Shortest Path Algorithms=
 
* [[Breadth-First Search-based Shortest Path Algorithm]]
⚠️ Only breadth-first search gives the guarantee of the shortest path.
* [[Dijkstra's Shortest-Path Algorithm]]
 
* [[Bellman-Ford Shortest-Path Algorithm]]
=Algorithm=
* [[Shortest Path with Bidirectional Search]]
 
=<span id='All-Pairs_Shortest_Path_Algorithms'></span>All-Pairs Shortest Path Algorithms (APSP)=
The algorithm is (differences to the [[Graph_Search#BFS_Algorithm_Pseudocode|canonical BFS]] algorithm are emphasized):
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/VQStd/problem-definition
<font size=-1>
* [[Floyd-Warshall Algorithm]]
BFS_with_Shortest_Path(graph G, start vertex s)
* [[Johnson's Algorithm]]
  <font color=teal># All nodes are assumed unexplored</font>
  <font color=SlateGray>initialize a Queue Q (FIFO)
  mark s as explored</font>
  annotate s with distance 0
  <font color=SlateGray>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</font>
        annotate w with a distance dist(w) = dist(v) + 1
        <font color=SlateGray>add w to Q</font>
</font>
 
The distance computed on reachable node gives the "layer" and the distance from the start node s.
 
:::[[File:BFS_Layers.png|160px]]

Latest revision as of 23:16, 24 November 2021

External

Internal

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

All-Pairs Shortest Path Algorithms (APSP)

Retrieved from "https://kb.novaordis.com/index.php?title=Shortest_Path_in_a_Graph&oldid=86178"