2
$\begingroup$

If I apply Dijkstra's ,BFS or Bellman-ford algorithm on a disconnected Graph then will the output be a tree or a disconnected Graph only because even if we have a disconnected Graph and we run Dijkstra's algorithm on it then it will return shortest path in the connected component only , but we maintain a predecessor array in all the algorithms which has information about the parent from which the node learnt the path so it will values for all the vertices , so even if we have a disconnected Graph then still other vertices will also be printed .

So output is Graph right for all the algorithms whether the graph is undirected or directed ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

No. The output of Dikstra's algorithm is a set of distances to each node. It's not a graph or a tree. This is true no matter whether the input graph is connected or disconnected. The standard algorithm for Dijkstra's algorithm sets the distance correctly for all vertices in all components (not just the ones in the same connected component as the source). The standard algorithm doesn't print anything, so if you are printing something, you're probably adding something extra to the standard algorithm, and we can't analyze that without seeing what your variation of the algorithm is.

Improve this answer
$\endgroup$
4
  • $\begingroup$ For instance I talk about DFS algorithm , its Output: All vertices reachable from v labeled as discovered . Now if the vertices are not reachable , it would give a forest as Output , Note that I haven't made any changes to the original problem . $\endgroup$
    – radhika
    Commented Aug 4, 2018 at 9:18
  • $\begingroup$ Also for Dijkstra or Bellman-ford , they give shortest path from source vertex to every other vertex in the connected component of the graph . we say that shortest path doesn't have a cycle (ignoring the case of zero weighted cycle) , that means all the vertices in the shortest path form a tree right ? $\endgroup$
    – radhika
    Commented Aug 4, 2018 at 9:20
  • $\begingroup$ This what I want to confirm that do we consider this tree as the final information of the graph because if there had been any unreachable vertex from source then it's distance would have been marked as infinity so then we can't say that if we are at some vertex then if we backtrack to source vertex we will get a tree because we have a disconnected component here ,So the result may be a forest . $\endgroup$
    – radhika
    Commented Aug 4, 2018 at 9:20
  • $\begingroup$ I just want to know that if I give any disconnected graph to any of these algorithms , they will give information about the connected component of the graph only but no status about the disconnected component so If I trace back the order in which vertices are traversed during computation of shortest path , will I not get a tree for the connected component and vertices from other disconnected component would form a forest $\endgroup$
    – radhika
    Commented Aug 4, 2018 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.