Content deleted Content added
No edit summary |
Predecessor matrix for negative edge weights? |
||
Line 30:
:I think that's a good idea. IFAIK the "Warshall" part of the algorithm means that it will actually find the paths. If it is used to find just the distances, it should be called just "Floyd's algorithm". I may be wrong. Anyway, I say go ahead and make the changes. --[[User:Ropez|Ropez]] 28 June 2005 22:11 (UTC)
::It's done. BTW, there seems to be a problem regarding the predecessor assignment statement. See [[Talk:Floyd-Warshall algorithm/C plus plus implementation]] for details. --[[User:Netvor|Netvor]] 30 June 2005 19:25 (UTC)
== Predecessor matrix for negative edge weights? ==
I was wondering how the code must look to get a working predecessor matrix with negative edge weights. The following part of the code seems to consider "0" as "no conection" or does it?
'''if''' dist[i,j] > 0
pred[i,j] := i
I personally would rewrite this as something like:
'''if''' dist[i,j] < Infinity
pred[i,j] := i
where "Infinity" is used as "There is no connection between these nodes". The C++-implementation gives me the impression this is the right way. -- [[User:RealLink|RealLink]] 10:39, 2 September 2005 (UTC)
| |||