Shortest Paths & Bipartite Check

Traversal covers BFS, which finds shortest paths for free when every edge costs the same. This page covers what happens once edges have different costs - Dijkstra, Bellman-Ford, Floyd-Warshall, and the O(V + E) shortcut a DAG allows - how to recover the actual path rather than just its length, and one more BFS-powered question that has nothing to do with distance at all: is this graph 2-colorable?

1. Dijkstra's algorithm

BFS's shortest-path guarantee relies on one fact: every edge costs exactly 1, so "fewer edges" and "less total cost" mean the same thing. The instant edges have different weights, that stops being true - a path with more edges can still be cheaper overall. Dijkstra's algorithm is what BFS becomes once you let go of that assumption.

Checking flight prices, never committing.

You keep a running "best price found so far" to every city. Each step you go to the cheapest unfinished city you know a price for, and from there you check whether flying through it makes any of its neighbours' prices cheaper than what you'd already found - if it does, you update your notes and keep browsing. You never book a flight (finalize a distance) until you're sure nothing cheaper is still sitting on the table.

That "cheapest unfinished city" step is exactly a min-priority-queue pop, and the "does going through here make a neighbour cheaper" step is called relaxation: dist[v] = min(dist[v], dist[u] + weight(u, v)).

visualization loads as you reach it

import heapq

 

 

def dijkstra(graph, start):

# graph[u] = list of (v, weight)

dist = {start: 0}

pq = [(0, start)] # (distance, node)

while pq:

d, u = heapq.heappop(pq)

if d > dist.get(u, float("inf")):

continue # stale entry, a cheaper one already won

for v, w in graph[u]:

nd = d + w

if nd < dist.get(v, float("inf")): # relax: found a cheaper way to v

dist[v] = nd

heapq.heappush(pq, (nd, v))

return dist

A -> B costs 5 directly, but A -> C -> B costs 2 + 1 = 3 - cheaper despite touching more edges.

⚠

Dijkstra requires non-negative weights

Dijkstra assumes non-negative weights, and that assumption is load-bearing, not decorative. The whole algorithm rests on "once I pop the cheapest unfinished node, its distance can never improve later" - true only because every other path to it would have to go through a more expensive node first. A negative edge breaks that: a node could look expensive when popped, then get cheaper later via an edge that subtracts from the total. Popping it early locks in a distance that's actually wrong, and there's no way to "un-pop" it. If negative weights are possible, you need Bellman-Ford instead.

Mnemonic

"Dijkstra is BFS with a price tag instead of a hop count." Swap the FIFO queue for a min-heap keyed on distance, and swap "already visited" for "already finalized (popped once)" - the rest of the shape is identical.

2. Bellman-Ford

Bellman-Ford trades Dijkstra's speed for tolerance: it handles negative edge weights, and can even tell you when a graph has a negative cycle (a loop whose total weight is negative, which would let you shrink a path's cost forever by looping through it again). The idea is blunt but correct - relax every edge, V - 1 times over:

visualization loads as you reach it

def bellman_ford(num_nodes, edges, start):

# edges = list of (u, v, weight)

dist = [float("inf")] * num_nodes

dist[start] = 0

for _ in range(num_nodes - 1): # a shortest path has at most V-1 edges

for u, v, w in edges:

if dist[u] + w < dist[v]:

dist[v] = dist[u] + w

for u, v, w in edges: # one more pass: did anything still improve?

if dist[u] + w < dist[v]:

return None # negative cycle reachable from start

return dist

A shortest path visits each vertex at most once, so it has at most V - 1 edges.

V - 1 full relaxation passes are therefore always enough for every true shortest distance to have propagated through - each pass extends the longest correctly-relaxed path prefix by at least one more edge, in the worst case.

⚠

A relaxation on pass V means a negative cycle

If a relaxation still succeeds on the V-th pass, the graph has a negative cycle reachable from the start. Every real shortest path is already fully settled after V - 1 passes; anything still improving on pass V can only be improving because it's looping through a cycle that subtracts weight each time around - which means there's no true shortest distance at all, it can be made arbitrarily small by looping more.

Extracting the negative cycle

Detecting a negative cycle is one extra pass. Recovering which cycle it is takes a parent array and one observation: the vertex that relaxed on the V-th pass is on a negative cycle or downstream of one, so stepping back V times along parent is guaranteed to land you inside the cycle itself.

visualization loads as you reach it

def find_negative_cycle(num_nodes, edges):

# dist starts at 0 everywhere - equivalent to a virtual source feeding every

# vertex, so this finds a negative cycle ANYWHERE, not just one reachable

# from a chosen start.

dist = [0] * num_nodes

parent = [-1] * num_nodes

hit = -1

for _ in range(num_nodes): # V passes, not V-1: the last one is the test

hit = -1

for u, v, w in edges:

if dist[u] + w < dist[v]:

dist[v] = dist[u] + w

parent[v] = u

hit = v

if hit == -1:

return None # nothing improved on the last pass

 

for _ in range(num_nodes): # walk back V times to get INSIDE the cycle

hit = parent[hit]

cycle, v = [], hit

while True:

cycle.append(v)

v = parent[v]

if v == hit:

break

cycle.reverse()

return cycle

⚠

Negative-cycle vertices aren't always on the cycle

You cannot start collecting the cycle from the vertex that relaxed - it may only be reachable from the cycle, not on it. Following parent from there walks into the cycle and then loops forever inside it, so a naive "append until repeat" starts recording mid-approach and returns a path with a tail. Stepping back V times first is what guarantees you are on the cycle, because a walk of V steps backwards through at most V distinct vertices must have entered a repeat.

Mnemonic

Zero-initialised dist is a free virtual source. Setting every distance to 0 rather than inf (except the start) is the same as adding a super-source with a zero-weight edge to every vertex - so the algorithm answers "is there a negative cycle anywhere in this graph" instead of "reachable from s". That is usually the question that is actually being asked.

3. Floyd-Warshall: every pair at once

Dijkstra and Bellman-Ford both answer "from this one source, how far is everything?" Sometimes the question is "how far is everything from everything"

• and running a single-source algorithm V times is not the best answer. Floyd-Warshall answers all V^2 pairs in one triple loop, in O(V^3) time and O(V^2) space, and it is about twelve lines.

"Am I allowed to change planes at k?"

Start with only direct flights. Then, one airport at a time, ask: for every pair (i, j), is going i -> k -> j cheaper than the best i -> j I know so far? After you have offered every airport as a connection, every pair's answer uses whichever subset of connections is best - which is every possible route.

visualization loads as you reach it

def floyd_warshall(num_nodes, edges):

INF = float("inf")

dist = [[INF] * num_nodes for _ in range(num_nodes)]

for v in range(num_nodes):

dist[v][v] = 0 # zero cost to stay put

for u, v, w in edges:

dist[u][v] = min(dist[u][v], w) # min: survives parallel edges

for k in range(num_nodes): # k is the OUTERMOST loop

for i in range(num_nodes):

for j in range(num_nodes):

if dist[i][k] + dist[k][j] < dist[i][j]:

dist[i][j] = dist[i][k] + dist[k][j]

return dist

⚠

k must be Floyd-Warshall's outermost loop

k must be the outermost loop, and swapping it inward is the single most common Floyd-Warshall bug. The loop order encodes the DP: after iteration k, dist[i][j] is the best path using only vertices 0..k as intermediates. Put k innermost and you are instead asking "improve (i,j) using any single intermediate," which finds two-edge shortcuts and misses longer chains - it needs V repetitions to converge, and gives silently wrong (too large) answers without them. The bug does not throw, and it passes on small graphs where every shortest path happens to be short.

⚠

A negative diagonal means a negative cycle

A negative value on the diagonal means a negative cycle. Floyd-Warshall tolerates negative edges just like Bellman-Ford, and it reports negative cycles just as cheaply: after the triple loop, dist[v][v] < 0 for some v means there is a cycle through v with negative total weight, so no shortest path is well defined. Any pair (i, j) whose route can pass through such a v has a meaningless distance and should be treated as negative infinity, not as whatever number the table happens to hold.

Drop the weights and the same triple loop answers pure reachability - this is Warshall's algorithm for transitive closure, and it is the thing to reach for when V is small and you want the full "who can reach whom" table:

visualization loads as you reach it

def transitive_closure(num_nodes, adj):

reach = [[False] * num_nodes for _ in range(num_nodes)]

for u in range(num_nodes):

reach[u][u] = True

for v in adj[u]:

reach[u][v] = True

for k in range(num_nodes):

for i in range(num_nodes):

if reach[i][k]: # skip the row early if k is unreachable

for j in range(num_nodes):

if reach[k][j]:

reach[i][j] = True

return reach

Mnemonic

Floyd-Warshall is worth it when V^3 beats V runs of Dijkstra. Dijkstra V times is O(V * (V + E) log V); Floyd-Warshall is O(V^3) with a tiny constant and no heap. Dense graphs and small V (say under 400) favour Floyd-Warshall; sparse graphs with large V favour repeated Dijkstra. And if any edge is negative, repeated Dijkstra is not an option at all.

4. Shortest paths on a DAG: no priority queue needed

If the graph is a DAG, you do not need Dijkstra, and you are not blocked by negative weights either. Process the vertices in topological order and relax each one's outgoing edges as you reach it. By the time you process u, every path into u has already been considered, so dist[u] is final - the same "settled once and for all" guarantee Dijkstra pays a heap for, here handed over for free by the ordering.

visualization loads as you reach it

def dag_shortest_path(num_nodes, adj, start, topo_order):

# adj[u] = list of (v, weight); topo_order from Cycles & Ordering

INF = float("inf")

dist = [INF] * num_nodes

dist[start] = 0

for u in topo_order:

if dist[u] == INF:

continue # unreachable, nothing to propagate

for v, w in adj[u]:

if dist[u] + w < dist[v]:

dist[v] = dist[u] + w

return dist

Mnemonic

On a DAG, the topological order is the priority queue. O(V + E), negative weights allowed, and flipping the comparison to > gives the longest path - which is NP-hard on a general graph and trivial here. That asymmetry is why "is it a DAG" is always worth asking before reaching for anything heavier.

⚠

Longest path is easy on DAGs, NP-hard elsewhere

Longest path is easy on a DAG and NP-hard everywhere else, and the reason is cycles, not weights. On a general graph you can pad any path by looping, so "longest simple path" needs you to track which vertices are already used - which is the Hamiltonian-path problem (Eulerian & Hamiltonian). A DAG cannot loop, so no such bookkeeping exists and one pass suffices.

5. Recovering the actual path

Every algorithm above returns distances. Problems usually want the route. The fix costs one array and no extra asymptotic time: whenever a relaxation succeeds, record who caused it.

visualization loads as you reach it

def dijkstra_with_path(graph, start, target):

import heapq

 

dist = {start: 0}

parent = {start: None} # who discovered each node

pq = [(0, start)]

while pq:

d, u = heapq.heappop(pq)

if d > dist.get(u, float("inf")):

continue

if u == target:

break # settled: safe to stop early

for v, w in graph[u]:

nd = d + w

if nd < dist.get(v, float("inf")):

dist[v] = nd

parent[v] = u # record it in the SAME branch as the relax

heapq.heappush(pq, (nd, v))

 

if target not in parent:

return None # unreachable

path, node = [], target

while node is not None:

path.append(node)

node = parent[node]

path.reverse() # built target-to-start, so flip it

return path

The same one-line addition works for BFS (parent[v] = u at enqueue time) and Bellman-Ford (parent[v] = u inside the relaxation if). Floyd-Warshall needs a matrix instead of an array - store nxt[i][j], the first hop on the best i -> j route, and update it to nxt[i][k] whenever dist[i][j] improves through k; the path is then read off by repeatedly following nxt.

⚠

parent[v] = u must update with the distance

parent[v] = u must live inside the same if as the distance update. Writing it beside the for loop instead records the last neighbour examined rather than the one that won, so dist comes out correct while the reconstructed path is nonsense - often a path that is not even connected. The rule: the parent assignment and the distance assignment are one atomic pair.

⚠

A parent chain gives one path, not all paths

A parent chain gives you a shortest path, not all of them. If two routes tie, whichever relaxed last wins and the other is lost. Problems asking for every shortest path (or for a count of them) need a list of predecessors per vertex, appended to on a tie (nd == dist[v]) and reset on a strict improvement (nd < dist[v]) - and forgetting the reset is how you end up counting paths through a route that was later beaten.

6. Dijkstra beyond plain distance

Dijkstra's loop is more general than "shortest distance." Two knobs turn it into a family of algorithms, and both are worth recognising on sight.

Knob 1: the state is more than the vertex

The moment a problem adds a constraint that a path carries - a budget of stops, a set of collected keys, a remaining fuel level, how many walls you have broken - the vertex of the real graph is no longer just the node. It is (node, state), and the graph you are searching has one layer per state value.

visualization loads as you reach it

import heapq

 

 

def cheapest_within_k_stops(n, flights, src, dst, k):

adj = [[] for _ in range(n)]

for u, v, w in flights:

adj[u].append((v, w))

 

# best[node][stops_used] - the state is the PAIR, so the table is 2D

INF = float("inf")

best = [[INF] * (k + 2) for _ in range(n)]

best[src][0] = 0

pq = [(0, src, 0)] # (cost, node, stops used)

while pq:

cost, u, stops = heapq.heappop(pq)

if u == dst:

return cost # first pop of dst is optimal

if stops > k or cost > best[u][stops]:

continue # over budget, or a stale entry

for v, w in adj[u]:

if cost + w < best[v][stops + 1]:

best[v][stops + 1] = cost + w

heapq.heappush(pq, (cost + w, v, stops + 1))

return -1

⚠

Marking visited by node alone breaks this family

Marking visited by node alone is the bug that defines this whole family. A route can reach a node more expensively but with stops to spare, and that worse-looking state may be the only one that can finish. Collapsing the state to node throws it away and returns -1 or an inflated cost on inputs where an answer exists. The rule from implicit graphs applies verbatim: whatever identifies a vertex must be in the visited key - here (node, stops), not node.

A layered graph is k + 1 stacked copies of the original.

Every edge moves you across within a layer and down one layer. Nothing about Dijkstra changes; the graph is simply V * (k+1) vertices, and the complexity says so: O(E * k * log(V * k)). Once you see the layers, "add a constraint" stops being a new algorithm and becomes a bigger input.

Mnemonic

Constraint in the problem, dimension in the table. "At most k X" adds one index; two independent budgets add two. If the extra dimension is small (k up to a few hundred) this is the intended solution; if it is unbounded, the constraint is not really a state and you need a different formulation.

Knob 2: the combine and the compare

Dijkstra's correctness needs one property: extending a path must never make it better. Addition of non-negative weights has it - and so do several other operators, each giving a different algorithm from the same nine lines.

Relaxation	Heap orders by	Answers	Canonical problem
nd = d + w	smallest first	cheapest total cost	plain shortest path
nd = max(d, w)	smallest first	bottleneck: minimise the largest single edge on the path	LC 1631 Path With Minimum Effort, LC 778 Swim in Rising Water
nd = d * p	largest first (push -p)	most probable path, when every p is in [0, 1]	LC 1514 Path with Maximum Probability
nd = d + w, but w may be 0 or 1 only	a deque, not a heap	same as plain, in O(V + E)	0-1 BFS

Why max works where you might expect it not to.

Dijkstra only needs that a path's value cannot improve by getting longer. Adding an edge to a path can only raise or keep its maximum, never lower it - so once the cheapest-bottleneck vertex is popped, nothing can beat it later, exactly as with addition. The same argument covers multiplication by probabilities in [0, 1], which can only shrink a product. It fails for a negative weight because that genuinely can improve a path, which is why Bellman-Ford exists.

⚠

A bottleneck path isn't a shortest path

A bottleneck path is not a shortest path, and the two answers can differ wildly. Minimising the largest step and minimising the total are different objectives: a long chain of cheap steps wins on bottleneck and loses on total. Copying nd = d + w into a "minimum effort" problem by habit is the same class of mistake as copying Dijkstra's cumulative distance into Prim (MST) - the loop looks right and the objective is wrong.

Mnemonic

A bottleneck problem can also be solved as "binary search the answer, then plain BFS." Guess a threshold, delete every edge above it, ask whether the target is still reachable. That is O((V + E) log(max weight)) and often easier to get right under pressure than the max-relaxation Dijkstra. Both are accepted; knowing the pair means you always have a fallback.

Second-shortest, and k-shortest

The state-augmentation idea covers these too: keep the best k distances per vertex instead of one, and stop expanding a vertex after it has been finalised k times.

visualization loads as you reach it

import heapq

 

 

def kth_shortest_path(n, adj, src, dst, k):

counts = [0] * n # how many times each node was finalised

pq = [(0, src)]

while pq:

d, u = heapq.heappop(pq)

counts[u] += 1

if u == dst and counts[u] == k:

return d # the k-th pop of dst is the k-th shortest

if counts[u] > k:

continue # this node cannot contribute any more

for v, w in adj[u]:

heapq.heappush(pq, (d + w, v))

return -1

⚠

Second-shortest isn't "the second value pushed"

For second-shortest, "the second value ever pushed" is not the answer. The second-shortest path may revisit vertices and may share most of its edges with the shortest one, so it is the second time the target is popped that matters - not the second entry in the heap, and not the second-best distance recorded at some intermediate vertex. Note also that this returns the second-shortest walk: if the problem insists on a strictly different path or forbids revisits, this is not the right tool.

A* is the same loop with the heap keyed on d + h(v) instead of d, where h estimates the remaining distance to the target. Set h = 0 and you have Dijkstra exactly. The estimate must never overestimate the true remaining distance (it must be admissible), or the first pop of the target stops being optimal - and on a grid, straight-line or Manhattan distance is admissible for free, which is why game pathfinding uses A* and shortest-path theory courses use Dijkstra.

7. Which algorithm

Situation	Use	Cost
Unweighted (or all weights equal)	BFS (Traversal)	O(V + E)
Every weight is 0 or 1	0-1 BFS with a deque (Traversal)	O(V + E)
Non-negative weights, one source	Dijkstra	O((V + E) log V)
Distance to the nearest of many sources	Multi-source BFS (Traversal)	O(V + E)
The graph is a DAG (any weights)	Topological order + relax, section 4	O(V + E)
Negative weights, one source	Bellman-Ford	O(V * E)
Need to detect a negative cycle	Bellman-Ford (a V-th pass still improving) or Floyd-Warshall (a negative diagonal)	as above
All pairs, small or dense V	Floyd-Warshall, section 3	O(V^3)
All pairs, large sparse V, no negative edges	Dijkstra from every vertex	O(V * (V + E) log V)
Cheapest subject to "at most k X"	State-augmented Dijkstra over (node, k), section 6	O(E * k * log(V * k))
Minimise the largest single step	Dijkstra with max relaxation, or binary search + BFS, section 6	O((V + E) log V)

Mnemonic

Read the weights first, the question second. Weights decide the family (equal to BFS, non-negative to Dijkstra, negative to Bellman-Ford, acyclic to topological order); the question only decides single-source versus all-pairs. Reaching for Dijkstra on an unweighted graph is not wrong, just a log V you did not need to pay - reaching for it on a graph with a negative edge is wrong.

8. Bipartite check via 2-coloring

A graph is bipartite if its vertices can be split into two groups such that every edge connects a vertex in one group to a vertex in the other - never two vertices in the same group. Equivalently: can you color every vertex with one of two colors so that no edge connects two same-colored vertices?

Class picture, two rows.

Line every student up in two rows so that every "these two are friends" edge always connects a kid in the front row to a kid in the back row - never two kids in the same row. If you can always do that, the friendship graph is bipartite.

This is a direct reuse of BFS from Traversal: color the start vertex, then every time BFS visits a neighbour, give it the opposite color of whoever discovered it.

visualization loads as you reach it

from collections import deque

 

 

def is_bipartite(graph, n):

color = [None] * n

for start in range(n):

if color[start] is not None:

continue

color[start] = 0

q = deque([start])

while q:

u = q.popleft()

for v in graph[u]:

if color[v] is None:

color[v] = 1 - color[u] # opposite color from whoever found it

q.append(v)

elif color[v] == color[u]:

return False # same-colored neighbours -> not bipartite

return True

⚠

Odd-length cycles are what make a graph non-bipartite

An odd-length cycle is exactly what makes a graph non-bipartite - nothing else can break it. Walk a cycle of length 3, alternating colors as you go: 0, 1, 0 - the third vertex wants color 0 again, but it's adjacent to the first vertex, which is also 0. Any odd cycle forces this same contradiction; any even cycle alternates back to the opposite color right on schedule and never conflicts. That's the entire theorem: a graph is bipartite iff it contains no odd-length cycle.

Mnemonic

"Bipartite check is BFS wearing a coloring book." Same queue, same visited-via-color-assignment - the only new idea is that a same-colored neighbour is a failure, not a skip.

Where to go next

MST & SCC picks up the other big weighted-graph question - not "what's the cheapest way to one destination" but "what's the cheapest way to connect everything at once."