Shortest Path

# Introduction

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.

page revision: 2, last edited: 25 Nov 2007 00:27