[BUG]Bug in C-Plus-Plus-Project/C-Plus-Plus3.5/graph/dijkstra.cpp
Closed this issue · 6 comments
Description
The current implementation contains a defect when handling graphs with 0 edges. While not guaranteed to crash, the algorithm may exhibit undefined behavior when processing empty adjacency lists. The issue stems from line 84 in dijkstra.cpp where the code unconditionally processes edges without first verifying if the adjacency list for the current node is empty. This could lead to either incorrect results or runtime errors depending on the implementation's memory behavior.
Expected behavior
The program proceeds with Dijkstra's algorithm normally despite having no valid edges
At line 84, it attempts to iterate through the adjacency list of each node ((*adj)[currentNode])
While this doesn't immediately crash (iterating empty vectors is technically valid in C++), it:
Wastes computation cycles checking empty edge lists
Reveals flawed assumptions in the algorithm's design
May lead to undefined behavior if the adjacency list implementation changes
The algorithm fails to explicitly handle this degenerate case, which is poor practice for graph algorithms
Actual behavior
When the input specifies 0 edges:
The program should safely handle graph traversal without attempting to access elements of empty adjacency lists
No undefined behavior should occur at line 84 where the algorithm currently iterates through edges of a node
For the source node (s), the distance should correctly be reported as 0
For all other nodes, the distance should be reported as unreachable (INF or -1)
The program should never attempt to dereference or iterate through non-existent edges
Steps to reproduce
No response
Context
I encountered this issue while testing the Dijkstra's algorithm implementation for edge cases. Specifically, I wanted to verify how the program handles:
Disconnected graphs (graphs with no edges between nodes)
Single-node graphs (edge case where vertices = 1 and edges = 0)
Instead of properly recognizing unreachable nodes or returning early for trivial cases, the algorithm proceeds with unnecessary computations on empty adjacency lists.
Additional information
No response
Thanks for catching this behavior! I agree that returning 0 in this edge-case seems unintended. Could you share a minimal test input that reproduces it? I’d be happy to help submit a PR to fix it.
Thanks for catching this behavior! I agree that returning 0 in this edge-case seems unintended. Could you share a minimal test input that reproduces it? I’d be happy to help submit a PR to fix it.
When prompted, enter:
Number of vertices: 1
Number of edges: 0
s: 0
t: 0
The error occurs
Hi, I’d love to work on this issue!
Just to note, this would be one of my first contributions.
This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.
Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!
Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!