34 views
1.) Dijkstras shortest path algorithm works on disconnected graph.

2.) Bellman ford algorithm works on disconnected graph.

Which of the above statements is/are true?
| 34 views
0

They should both work, I don't see a reason why they won't. The shortest paths to the unreachable nodes will be infinity (Unless there is a specific implementation where it won't work).
It is equivalent to running the algorithms on a directed graph where a node cannot be reached from a start node.

Edit: to test:

https://www-m9.ma.tum.de/graph-algorithms/spp-bellman-ford/index_en.html

https://www-m9.ma.tum.de/graph-algorithms/spp-dijkstra/index_en.html

Just right click on edges to delete them and disconnect a node.

0

yeah I too think both are true because in both algos,initially the distance from starting vertex to every other vertex will be kept $\infty$.So even if the graph is disconnected the distances from starting vertex to those vertices in other components remain $\infty$ when the algorithm terminates.

0
Thanku shashin and pranay562