Stony Brook Algorithm Repository

Shortest Path


Input Description: An edge-weighted graph \(G\), with start vertex \(s\) and end vertex \(t\).
Problem: Find the shortest path from \(s\) to \(t\) in \(G\).

Excerpt from The Algorithm Design Manual: The problem of finding shortest paths in a graph has a surprising variety of applications:


Boost Graph Library (rating 10)
Goldberg's Network Optimization Codes (rating 10)
algorithms.js (rating 9)
java-algorithms-implementation (rating 9)
C-Sharp-Algorithms (rating 9)
AlgoDS (rating 9)
C++ Boost Library (rating 9)
JGraphT (rating 9)
RAPID (rating 8)
goraph (rating 7)
LEDA (rating 7)

Recommended Books

The Boost Graph Library: user guide and reference manual by J. Siek and L. Lee and A. Lumsdaine Network Flows : Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin

Related Problems

Connected Components

Graph Isomorphism

Matrix Multiplication

Motion Planning

Network Flow

Priority Queues

Steiner Tree

Transitive Closure and Reduction

Go To Main Page