what is the algorithm in distance graph

[zhenyu]

In the code, there is the Bellmanford algorithm in class
"DistanceGraph ", but I am confused by the parameters in the function,
such as potential, distance, depth. what is those parameters meaning?
Is that the standard bellmanford, or Johnson? Is there any reference
papers about it?

[phm]

It started out as the Bellman-Ford algorithm, but it was subsequently
modified to try to avoid wasted re-propagations, so that it is now a
hybrid between Bellman-Ford and the Dijkstra algorithm. Basically, it
adopts the potential function idea of Johnson's algorithm to use a
previous assignment that is almost a solution to implicitly re-weight
the edges so that almost all the edges are non-negative. (It doesn't
actually re-weight the edges but calculates the priorities as if they
were re-weighted.) This allows a priority queue as in the Dijkstra
algorithm to direct the propagation to make it unlikely that there
will be more than one propagation from a node. However, unlike pure
Dijkstra, it does allow re-propagations because a few of the re-
weighted edges may still be negative.

[zhenyu]

through tracing the "bellmanford" algorithm, I found that only the
negative weight was considered in the process, which identifies lower
bound of variable(time point). Because the initial value of potential
is 0, all the positive weight will never be lower than 0.
Is that true for the algorithm?
Is there any mathematical proof? Or is that complete?

[Liu Yuechang]

For the decision of Simple Temporal Problem (STP), that is true and complete.

Just imagine such non-equationial system like: x-y<=0, y-z<=0, z-x<=-1,

0<=-1 follows, which is of course not true.

LIU

2011/9/13 zhenyu <zheny...@gmail.com>

--
You received this message because you are subscribed to the Google Groups "europa-users" group.
To post to this group, send email to europa...@googlegroups.com.
To unsubscribe from this group, send email to europa-users...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/europa-users?hl=en.