CODEWITHSUNDEEP
algorithmpath-finding
Bozhidar Grujoski
Bozhidar Grujoski

Reputation: 78

Floyd's Shortest Path Algorithm?

I think I'm having some issues here Here's the matrix I'm given enter image description here

I'm supposed to find the costs of paths passing through vertex k = 0, 1, 2, and 3. For vertex k=0, have

0, 10, 30, inf

15, 0, inf, inf

inf, 5, 0, 2

30, 40, 33, 0

Is that correct? Is anyone able to help me out?

Upvotes: 2

Views: 112

Answers (2)

Codor
Codor

Reputation: 17605

To my understanding, the intermediate result for k=1 would be as follows.

000 010 003 inf
015 000 018 inf
inf 005 000 002
030 004 033 000

For intutitive understanding, the entry with indices i and j would be the shortest path from i to j where intermediate noted from the set {1} are permitted, i.e. the better path from either going from i to j or the path i-0-j.

Upvotes: 1

Michael F
Michael F

Reputation: 40830

Let's try to interpret your (intermediate?) result. The first line reads:

0, 10, 30, inf

Which means that there's a path from vertex 0 to 0 with 0 cost, trivially, a path from vertex 0 to 1 with minimum cost 10, and a path from vertex 0 to 2 with minimum cost 30. This cannot be, as there is an even cheaper path from vertex 0 to 2, with cost 3, given by the initial cost matrix. Therefore your implementation has a bug. If you could share it, we might also be able to point it out.

PS. Even if it were an intermediate result, costs in the matrix will never increase by Floyd-Warshall, only decrease. (Ex: prove it)

Upvotes: 0

Related Questions