Floyd-Warshall Algorithm doesn't work with this test case.
Closed this issue · 1 comments
bdparrish commented
How is NULL the correct answer?
i == j := 0 && You have two directed paths from 2 -> 2 with different weights.
stanford-algs/testCases/course4/assignment1AllPairsShortestPath/input_random_1_2.txt
beaunus commented
@bdparrish Thank you for your interest in this project. The reason this particular case has a NULL answer is this:
- The graph contains a negative cycle. Thus, you could take the negative cycle infinitely many times, making the "shortest" path negative infinity.
The negative cycle is the path from 1 --> 1, with a weight of -73.
The assignment reads:
If each of the three graphs has a negative-cost cycle, then enter "NULL" in the box below
In our adaptation, if the graph has a negative cycle, the answer is NULL.
Please share if you have any further thoughts or questions.