1.4.4 Shortest Path

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: An edge-weighted graph G , with start vertex and end vertex t .

Problem: Find the shortest path from to t in G .

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)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
  • Combinatorica (Mathematica) (rating 3)
  • The Stanford GraphBase (C) (rating 3)

    Related Problems

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

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .