[BUG]Bug in C-Plus-Plus-Project/C-Plus-Plus3.5/graph/dijkstra.cpp

[18781875724]

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

[MQ-06]

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.

[18781875724]

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