Beej's Bit Bucket
a day ago
- Dijkstra's algorithm finds the shortest path between nodes in a graph with non-negative edge weights.
- The algorithm maintains a set of unvisited cities, initializing distances as infinite except for the start (zero).
- It repeatedly selects the unvisited city with the smallest known distance and relaxes its neighboring cities.
- Relaxation updates a neighbor's distance and parent pointer if a shorter path via the current city is found.
- Parent pointers trace the shortest route back to the start once the destination is reached.
- The algorithm fails with negative edge weights, as it assumes no shorter path can be found later.
- Edge weights can be adjusted for real-world constraints like ferry routes, bicycle paths, or steep roads.