Weighted Graph

Every edge carries a cost (distance, latency, price). "Shortest" now means minimum total weight, not fewest hops — BFS is no longer enough.

What to know

Dijkstra requires non-negative weights; one negative edge breaks its greedy proof.
Bellman-Ford tolerates negative edges and detects negative cycles with one extra relaxation round.
Floyd-Warshall computes all-pairs distances with three nested loops.
A* = Dijkstra + admissible heuristic; it never expands more nodes than Dijkstra.

In the wild: Google Maps routing, network latency optimization, flight price search, game NPC pathfinding.

Dijkstra (min-heap)

O((V + E) log V)

Single-source shortest path, non-negative weights

Bellman-Ford

O(V · E)

Shortest path with negative edges, arbitrage detection

Floyd-Warshall

O(V³)

All-pairs shortest paths on small dense graphs

A* search

O(E log V), often far less

Goal-directed pathfinding with a heuristic

Each problem has its own page: progressive hints, how to approach it, and the full solution.

Network Delay Time

Hints → approach → solution

Cheapest Flights Within K Stops

Hints → approach → solution

Path With Minimum Effort

Hints → approach → solution