Latest revision as of 23:16, 24 November 2021

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

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)

@@ Line 4: / Line 4: @@
 =Internal=
-* [[Graphs#Subjects|Graphs]]
+* [[Graphs#Graph_Algorithms|Graphs]]
 * [[Graph_Search#Breadth-First_Search_.28BFS.29|Graph Search &#124; 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.
-=The Problem=
-The '''single-source shortest paths''' is formally defined as follows: given a directed graph G=(V, E) , with n = │V│ and m=│E│, where each edge has a '''non-negative''' length ℓ<sub>e</sub>, and a [[Graph_Concepts#Source_Vertex|source vertex]] s, compute for
 =Shortest Path Algorithms=
 * [[Breadth-First Search-based Shortest Path Algorithm]]
 * [[Dijkstra's Shortest-Path Algorithm]]
+* [[Bellman-Ford Shortest-Path Algorithm]]
+* [[Shortest Path with Bidirectional Search]]
+=<span id='All-Pairs_Shortest_Path_Algorithms'></span>All-Pairs Shortest Path Algorithms (APSP)=
+* https://www.coursera.org/learn/algorithms-npcomplete/lecture/VQStd/problem-definition
+* [[Floyd-Warshall Algorithm]]
+* [[Johnson's Algorithm]]

Shortest Path in a Graph: Difference between revisions