Shortest Path


Shortest path refers to a graph theory problem in which one wishes to find the shortest path between two vertices. Single source shortest path is where you are given a starting node and wish to find the minimal distance to every other node. All pairs shortest path is where you want to find the shortest path between every pair of two vertices. There are quite a few algorithms suited for this problem. They are:

List of Algorithms

Single source algorithms

Dijkstra's Algorithm - $O(E+V^2)$ normally, $O((E+V)\log V)$ with a binary heap, $O(E + V\log V)$ with a fibonacci heap. Only works for positive edge-weights.
Bellman-Ford - $O(EV)$. Works for graphs with negative edge weights

All pairs algorithms

Floyd-Warshall - $O(V^3)$. Very short code to write, easy to remember.
Any single source shortest path run from each vertex. Dijkstra's has a best case running time of $O(EV + V^2\log V)$ with this method.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License