All lessonsOpen Open Open Open Open
10. Graphs
Shortest paths
0 of 5 activities0%
Reading 1
Distances on graphs
Unweighted: BFS distances. Nonnegative weights: Dijkstra with a priority queue — O((V+E) log V) typical. Negative weights: Bellman-Ford (detects negative cycles). All pairs: Floyd-Warshall O(V^3).
Do not use Dijkstra with negative edges.
Check 2
Dijkstra constraint
Dijkstra assumes edge weights are
Fill in 3
Unweighted
Try it 4
Relax idea
If dist[u]+w < dist[v] update.
main.cpp
Loading editor…
Output will appear here.
Assignment 5
Path length unweighted
Read distance d already computed; print d.
main.cpp
Loading editor…