Stony Brook Algorithm Repository


Shortest Path

Input
Output

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:


Implementations

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