Awesome q2a theme
0 votes
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?
in Algorithms by (135 points) | 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

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Feb 2020
  1. shashin

    363 Points

  2. Shaik Masthan

    79 Points

  3. SuvasishDutta

    39 Points

  4. srestha

    33 Points

  5. Mk Utkarsh

    32 Points

  6. neeraj_bhatt

    31 Points

  7. !KARAN

    30 Points

  8. Debapaul

    23 Points

  9. Pratyush Priyam Kuan

    18 Points

  10. kalra05

    18 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
3,314 questions
1,581 answers
10,271 comments
89,904 users