4 / 6 Shortest Paths

Three Ways To Break

You have a working heap Dijkstra: visited[v] is set when v is popped, popped vertices are skipped, and edges relax with if (dist[v] + w < dist[to]). Input weights are positive integers.

More than one option applies. Which of these changes can make it return a wrong distance?

A

Some vertices are unreachable from the source and keep distance INF.

B

A self-loop of weight 0 is added at every vertex.

C

Distances are stored in a 32-bit signed int on a graph where the shortest path sums to about 4×1094 \times 10^9.

D

One edge weight is changed from 3 to -1, with no cycle in the graph becoming negative.

E

visited[u] is set when u is pushed instead of when it is popped.

F

Heap ties are broken by smaller vertex index instead of insertion order.