Specific Graph and some claims on shortest path?
I stuck in one challenging question, I read on my notes.
an Undirected, Weighted and Connected Graph G , (without negative weight and all weights are distinct ) is given, we know in this graph the shortest path between any two vertexes is on Minimum Spanning Tree (MST). (for any pair of vertices and for any shortest path between them, it lies on MST). Which of The following Is True ?
1) Graph G is a Tree.
2) weight of each {u,v} edge, at least is equal (same) to heaviest edge in shortest path from u to v .
3) shortest path between any two vertex u , v is unique.
4) suppose start from vertex s , Prime (for calculating MST) and Dijkstra (for calculating shortest path), process and add the vertexes into their Trees, with the same order. (two algorithm works with same order in processing and adding node)
How can verify me these options? This is a challenging question.
No. For example: V = {1, 2, 3} , E = {(1, 2, 1), (2, 3, 2), (1, 3, 4)} (each edge is encoded as a tuple (one vertex, another vertex, weight)). It is not a tree, but all shortest path are on the minimum spanning tree.
Yes. If the weight of this edge is less than the weight of the heaviest edge which is in the shortest path, this edge is shorter than the shortest path(because there are no edges with negative weight). Thus, the shortest path is not the shortest. It is a contradiction.
No*. Let's assume that we have a graph with two vertices {1, 2} and one edge between them with zero weight. There are infinitely many shortest paths between the first and the second vertex( [1, 2], [1, 2, 1, 2], ... )
*However, there is a unique simple shortest path between any two vertices because there is only one simple path between any two vertices in a tree, any path which does not fully lie in a minimum spanning tree is longer due to the problem statement and there is only one minimum spanning tree in a graph with distinct edges weights.
No. Consider this tree: V = {1, 2, 3, 4} , E = {(1, 2, 3), (2, 3, 2), (1, 4, 4)} . Let's assume that the start vertex is 1 . Prim's algorithm will take the first vertex, than the second one, than the third one and only after this the fourth. But Dijkstra's algorithm will take the fourth vertex before the third one. It happens because the third vertex is located closer to the tree after processing the first two vertices, but it the total distance to it from the start node is larger.
I do not want to give the complete answer, but here is how you approach it:
Can you add edge[s] to the tree such that it is not a tree anymore and still the tree contains all the shortest paths?
What happens if there is an edge that is shorter than the heaviest edge?
it is confusing because the problem says "the shortest path between any two vertexes is on MST", but doesn't address the fact that there might be multiple shortest paths. So you can probably assume that "at least one shortest path lies on the tree". In which case just connect two vertices with an edge whose weight equals to cost through the MST, and you get the answer.
Again, you should start with what happens if the vertices are not added in the same order
上一篇: 定向非循环图中的最短路径具有小的程度
下一篇: 具体图和一些关于最短路径的声明？