beaunus/stanford-algs

Wrong testcase in stanford-algs/testCases/course2/assignment2Dijkstra/input_random_10_16.txt

Closed this issue · 1 comments

dasarchana commented

Directed edge distance from 124 to 143 is 13, but directed edge distance from 143 to 124 is 1194.
Spent over 3 days finding out why solution does not match.

dgrcode commented

Thank you very much for raising this issue 🙌

Could you open a PR with a fix for this problem? I'm assuming only one of the two pairs is incorrect. Could you find out which one is it? I suggest you update one of the two and run your Dijkstra algorithm. If the result is different than the expected output, then it must be the other pair.

PS: The fact that you found this issue is great for this project, but it could be a sign that your Dijkstra algorithm can be optimized. I mean, let's say you first visit 124, and from there you visit 143. Once you're in 143 you should not include 124 in "nodes pending to be visited", as you've already been there. It seems your algorithm might be backtracking.