In [ ]:
from IPython.display import display
from IPython.display import HTML
import IPython.core.display as di # Example: di.display_html('<h3>%s:</h3>' % str, raw=True)
# This line will hide code by default when the notebook is exported as HTML
di.display_html('<script>jQuery(function() {if (jQuery("body.notebook_app").length == 0) { jQuery(".input_area").toggle(); jQuery(".prompt").toggle();}});</script>', raw=True)
# This line will add a button to toggle visibility of code blocks, for use with the HTML export version
di.display_html('''<button onclick="jQuery('.input_area').toggle(); jQuery('.prompt').toggle();">Toggle code</button>''', raw=True)
Shortest paths are not always unique: sometimes there are two or more different paths with the minimum possible length. Show how to solve the following problem in $O((|V| + |E|)\log|V|)$ time.
Input: An undirected graph $G = (V, E)$; edge lengths $l_e > 0$; starting vertex $s \in V$.
Output: A Boolean array usp[.]: for each node $u$, the entry usp[u] should be true if and only if there is a unique shortest path from $s$ to $u$. (Note: usp[s] = true.)
This will run in the required time when the heap is implemented as a binary heap.
Correctness: By Djikstra's proof of correctness, this algorithm will identify the shortest paths from the source $u$ to the other vertices. For uniqueness, we consider some vertex $v$. If there are multiple shortest paths, then they either all share the same final edge $(w, v)$ (for some vertex $w$), or they have different final edges. In the former case, there must be multiple shortest paths from $u$ to $w$. This will be detected in the first conditional statement when the algorithm explores from $w$ and updates the distance to $v$ by taking edge $(w, v)$. In the latter case, the algorithm will detect the existence of multiple shortest paths with the second conditional statement by testing for equality of two distances.
In [ ]: