Description
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