Shortest Path in a Graph: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 7: | Line 7: | ||
* [[Graph_Search#Breadth-First_Search_.28BFS.29|Graph Search | Breadth-First Search]] | * [[Graph_Search#Breadth-First_Search_.28BFS.29|Graph Search | Breadth-First Search]] | ||
=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 | 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 Problem= | ||
=Shortest Path Algorithms= | =Shortest Path Algorithms= | ||
* [[Breadth-First Search-based Shortest Path Algorithm]] | * [[Breadth-First Search-based Shortest Path Algorithm]] | ||
* [[Dijkstra's Shortest-Path Algorithm]] | * [[Dijkstra's Shortest-Path Algorithm]] | ||
Revision as of 19:23, 14 October 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.