Shortest Path Problem

From: MimsyBoro (eytan_at_tradertools.com)
Date: 03/25/05

  • Next message: Craig Feinstein: "Re: factoring integers on a classical computer in polynomial-time" 
    Date: 25 Mar 2005 05:39:24 -0800

    Hello,
    I'm trying to solve the following problem in algorithms.

    I'm given a weighted graph G and the results of running Dijsktra on it.
    It is also stated that a path exists that is also a shortest path
    weight-wise and also a shortest path length-wise (vertex-wise).

    Now replace the weight function w with the function w-1 and find the
    weight of the shortest path (weight-wise).

    I think that you are supposed to prove that all the infotmation is
    useless (the shortest-path weight/vertex wise and the previous results
    of Dijsktra) becuase now anything can happen. But I don't know how to
    prove it.

    Any suggestions?

    Thanks In Advance

  • Next message: Craig Feinstein: "Re: factoring integers on a classical computer in polynomial-time"