find shortest path between 2 vertices using BFS algorithm

Question

I have this question for homework:

prove/disprove:

A. Given an unintentional bound graph G (V, E) and a minimum spanning tree for this graph, and 2 vertices u, v, the shortest path between u and v in graph G can be found by performing BFS on the tree T.

B. Given a directed graph G (V, E) with weights and vertex s. The number of arcs in the shortest distance tree of this graph from the origin of s is the | V | -1.

I think that's true but can't prove it.

Can someone help me?

Shuki Avraham · Accepted Answer · 2020-07-06 15:45:47Z

2

A. Not true, the minimum spanning tree does not contain all the shortest paths. example:

The MST is the black edges (weight=1) the red edge (weight=2) is the shortest path between its nodes.

B. True, suppose you have a shortest paths graph with |V| edges, than there is a node v with at least two path from s (let v be the closest node to s with that property), in that case you can remove one of the incoming edges of v without changing the weights of the paths to all the nodes

answered Jul 6, 2020 at 15:45

Shuki Avraham

1,0531 gold badge7 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

אנונימי Over a year ago

The answer for B was false also.

Collectives™ on Stack Overflow

find shortest path between 2 vertices using BFS algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related