Shortest Paths

A shortest path is the route whose edge weights add up to the least, and the topic teaches the three algorithms that find one in a weighted graph. It opens on the decision that chooses between them, with breadth-first search as the unweighted case. Dijkstra's algorithm follows, traced vertex by vertex with its distances, settled set and queue kept apart, then written in Python, Java and TypeScript. Bellman-Ford comes next, with a trace of why V − 1 passes are enough and how one more finds a negative cycle, and its code. Floyd-Warshall fills a table for every pair, one stop at a time, and its code rebuilds a path. A comparison sets the three side by side, a gotcha runs Dijkstra's algorithm on a negative edge, and an exercise plans ferry fares before and after a rebate.