Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source.
In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?
- $P,Q,R,S,T,U$
- $P,Q,R,U,S,T$
- $P,Q,R,U,T,S$
- $P,Q,T,R,U,S$