The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.4.4 Shortest Path

Problem Input | Problem Output

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:


  • Goldberg's Network Optimization Codes (C) (rating 10)
  • Boost: C++ Libraries (C++) (rating 9)
  • JGraphT: Java graph library (Java) (rating 9)
  • RAPID - Robust and Accurate Polygon Interface detection (C,FORTRAN) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • Discrete Optimization Methods (Pascal) (rating 4)

  • 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 Links

  • 9th DIMACS Implementation Challenge: Shortest Paths

    Related Problems

    Connected Components
    Graph Isomorphism
    Matrix Multiplication
    Motion Planning
    Network Flow
    Priority Queues
    Steiner Tree
    Transitive Closure and Reduction

    This page last modified on 2008-07-10 .