KEMBAR78
Fix bugs in dijkstra algorithm and csv parsing by reki2000 · Pull Request #8 · reki2000/langs-bench-dijkstra · GitHub
Skip to content

Conversation

@reki2000
Copy link
Owner

Fixes three bugs and one refactoring

  1. Dijkstra loop should check if the popped (from priority queue) distance for node i is smaller than calculated distance d[i]. This r reduces the complexity of main the loopto O( (|V|+|E| log |V|) - don't know the original's complexity - Thanks TsumoiYorozu !

  2. Fill distance array d in Dijkstra loop with enough big value like INT32_MAX to reduce d[i] == 0 (checks if the node has been already visited)

  3. CSV parsing logic has a critical bug - parses integer without decimal dot to x1000 instead of x100.

  4. Use Int32 for Distance type explicitly. But still not completed over all languages in this benchmark.

@reki2000 reki2000 merged commit 95f4dab into master Jun 22, 2020
@wx257osn2
Copy link
Contributor

CSV parsing logic has a critical bug - parses integer without decimal dot to x1000 instead of x100.

😱 I apologize for that...

@reki2000
Copy link
Owner Author

reki2000 commented Jun 22, 2020

@wx257osn2 いえ、元のコードからあったバグで、修正いただいたおかげて発見できました!

@reki2000 reki2000 deleted the fix/minimum-check-after-pop branch July 16, 2022 08:02
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants