Floyd's warshall algorithm infinity

Question

I'm working on implementing the floyd warshall algorithm. I apply this algorithm on a graph with different vertices and some of them are not linked. My code isn't getting the right answer.

The final path generated from one vertex to another sometimes includes an edge which doesn't exist. I think my error comes from the fact that I compare infinity to infinity. I currently do that: I assume that a big integer will represent infinity for example 10000. What should I do when I met a situation like that 10000 > 10000 + n? with n < 10000

What is the maximum weight of an edge? Are there edges with negative weights? — kraskevich
And what do you mean by 10000 > 10000 + n? It is true for any n < 0, but how is this related to your question? — kraskevich
The maximum weight is 1000 and there is no edge with negative weights — mel
10000 represent the infinity but in fact we cannot compare to infinity, so is there a special case in floyd warshall algorithm for this kind of thing? — mel
If the infinity is big enough, there is no need handle it specially. — kraskevich

kraskevich kraskevich · Accepted Answer · 2015-01-13T18:45:12

The longest possible valid path can have length = (n - 1) * 1000. Thus, "infinity" must be strictly greater than this value. And there is no need to handle it specially as long as 2 * infinity fits into the type you are using to store distances.

Floyd's warshall algorithm infinity

1 Answers