103 views
1 1 vote

Let $G=(V,E)$ be a dag, where each edge is annotated with some positive length. Let $s$ be a source vertex in $G$.

Suppose we run Dijkstra's algorithm to compute the distance from $s$ to each vertex $v \in V$, and then order the vertices in increasing order of their distance from $s$.

Are we guaranteed that this is a valid topological sort of $G$?

  1. Yes
     
  2. No

1 Answer

1 1 vote

A topological ordering depends on the direction of edges, not on shortest-path distances.

For every edge, $u \rightarrow v$ a topological ordering requires $u$ before $v$

But it is possible for $v$ to have a shorter distance from the source than $u$ because $v$ may have another shorter path.

Consider this DAG:

$s \rightarrow v$ with weight $1$

$s \rightarrow u$ with weight $10$

$u \rightarrow v$ with weight $1$

The shortest-path distances are:

$d(s)=0$

$d(v)=1$

$d(u)=10$

Therefore, ordering vertices by increasing distance gives:

$s,v,u$

But the graph contains:

$u \rightarrow v$

So every valid topological ordering must place:

$u$ before $v$

The distance ordering puts $v$ before $u$.

Therefore it is not a valid topological ordering.


Answer: B

Answer:
Position:
Show:

Related questions

2 2 votes
1 1 answer
99
99 views
GO Classes asked Aug 19
99 views
Which of the following is a valid topological ordering of the vertices in the given graph?$0 \rightarrow 6 \rightarrow 1 \rightarrow 7 \rightarrow 3 \rightarrow 5 \righta...
2 2 votes
1 1 answer
118
118 views