Shortest-path algorithm conditions
Edge weights determine which shortest-path method applies.
Key knowledge
BFS finds shortest paths measured by number of edges in an unweighted graph. Dijkstra's algorithm computes single-source minimum-weight distances when every edge weight is nonnegative, repeatedly settling the smallest tentative distance.
Conditions and scope
- The graph is finite and the source is specified; unreachable vertices have infinite distance.
- Negative edge weights invalidate Dijkstra's general guarantee; path weights use sums of edge weights.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Massachusetts Institute of Technology2 sources
Evidence and review
Graph definitions, adjacency representations, edge-count distances and BFS shortest paths. Nonnegative-edge assumption, monotone shortest-path distances and Dijkstra's algorithm.
2026-10-10 · Unweighted BFS and nonnegative-weight Dijkstra, excluding unrestricted negative-edge algorithms.
Entry details
Permanent link to this entry ↗- Record identity
- info-shortest-paths
- Revision
- university-reference.1
- Structured reference record
- University reference