Shortest Path in a Graph: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 14: Line 14:
=TODO=
=TODO=
<font color=darkgray>Reshape this page to accommodate [[Dijkstra's Algorithm]].</font>
<font color=darkgray>Reshape this page to accommodate [[Dijkstra's Algorithm]].</font>
=Algorithm=
The algorithm is (differences to the [[Graph_Search#BFS_Algorithm_Pseudocode|canonical BFS]] algorithm are emphasized):
<font size=-1>
BFS_with_Shortest_Path(graph G, start vertex s)
  <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]]

Revision as of 19:19, 14 October 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.

The Problem

Shortest Path Algorithms

TODO

Reshape this page to accommodate Dijkstra's Algorithm.

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