Dijkstra's Shortest-Path Algorithm: Difference between revisions
| Line 7: | Line 7: | ||
The problem of computing the shortest path in a graph can be solved with bread-first search, but the [[Breadth-First_Search-based_Shortest_Path_Algorithm|breadth-first search-based shortest path algorithm]] works in the special case when the [[Graph_Concepts#Edge_Length|length]] of every edge in the graph ℓe is 1. Dijkstra's shortest-path algorithm solves a more general problem, where the edges have arbitrary non-negative lengths. | The problem of computing the shortest path in a graph can be solved with bread-first search, but the [[Breadth-First_Search-based_Shortest_Path_Algorithm|breadth-first search-based shortest path algorithm]] works in the special case when the [[Graph_Concepts#Edge_Length|length]] of every edge in the graph ℓe is 1. Dijkstra's shortest-path algorithm solves a more general problem, where the edges have arbitrary non-negative lengths. | ||
The problem of computing the shortest path in a graph with arbitrary edge lengths can be theoretically reduced to the problem of computing the shortest path in a graph with edges of length ℓe=1, by replacing an edge with an arbitrary length n with n edges with length 1, and adding extra vertices. | The problem of computing the shortest path in a graph with arbitrary edge lengths can be theoretically reduced to the problem of computing the shortest path in a graph with edges of length ℓe=1, by replacing an edge with an arbitrary length n with n edges with length 1, and adding extra vertices. The breadth-first search-based shortest path algorithm will work fine in this situation, producing the same results as the Dijkstra's algorithm, but the problem is that we are increasing the size of the graph, in terms of adding extra nodes and edges, and this increase my be non-trivial: for an edge with length 1000, we need to add extra 999 edges and 999 extra nodes. | ||
=The Problem= | =The Problem= | ||
Revision as of 20:23, 14 October 2021
External
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/rxrPa/dijkstras-shortest-path-algorithm
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/iIzo8/heaps-operations-and-applications
Internal
Overview
The problem of computing the shortest path in a graph can be solved with bread-first search, but the breadth-first search-based shortest path algorithm works in the special case when the length of every edge in the graph ℓe is 1. Dijkstra's shortest-path algorithm solves a more general problem, where the edges have arbitrary non-negative lengths.
The problem of computing the shortest path in a graph with arbitrary edge lengths can be theoretically reduced to the problem of computing the shortest path in a graph with edges of length ℓe=1, by replacing an edge with an arbitrary length n with n edges with length 1, and adding extra vertices. The breadth-first search-based shortest path algorithm will work fine in this situation, producing the same results as the Dijkstra's algorithm, but the problem is that we are increasing the size of the graph, in terms of adding extra nodes and edges, and this increase my be non-trivial: for an edge with length 1000, we need to add extra 999 edges and 999 extra nodes.
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 e has a non-negative length ℓe, and a source vertex s, compute for each v ∈ V the length L(v) of the shortest path s → v.
The assumption that the length is non-negative is important. Dijkstra's shortest-path algorithm does not work correctly in presence of negative length edges.
Speed Up
The Dijkstra's algorithm can be speed up with the use of a heap.