title: Differences between Minimum Spanning Tree and Shortest Path Tree
body: <p>Here is an exercise:</p>
  
  <blockquote>
    <p>Either prove the following or give a counterexample:</p>
    
    <p>(a)  Is the path between a pair of vertices in a minimum spanning tree
    of an undirected graph necessarily the shortest (minimum weight) path?</p>
    
    <p>(b)  Suppose that the minimum spanning tree of the graph is unique. Is
    the path between a pair of vertices in a minimum spanning tree of an
    undirected graph necessarily the shortest (minimum weight) path?</p>
  </blockquote>
  
  <p>My Answer is</p>
  
  <p>(a)</p>
  
  <p>No, for example, for graph 0, 1, 2,  0-1 is 4, 1-2 is 2, 2-0 is 5, then 0-2’s true shortest path is 5, but the mst is 0-1-2, in mst, 0-2 is 6</p>
  
  <p>(b)</p>
  
  <p><strong>My problem comes into this (b).</strong> </p>
  
  <p>I don't understand how <code>whether the MST is unique</code> can affect the shortest path.</p>
  
  <p>First, my understanding is that when the weights of edges are not distinct, multiple MST may exist at the same time, right?</p>
  
  <p>Second, even if MST is unique, the answer of (a) above still applies for (b), right?</p>