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:

The best book available for this problem is Network Flows : Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.


Implementations

  • Goldberg's Network Optimization Codes (C) (rating 9)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • Discrete Optimization Methods (Pascal) (rating 5)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)
  • The Stanford GraphBase (C) (rating 3)
  • Combinatorica (Mathematica) (rating 3)

    Related Problems

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


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .