114 views
0 0 votes

Let $G=(V,E)$ be a directed graph with positive edge weights.

Given vertices $s,w,t$ we want the length of the shortest path from $s$ to $t$ that must pass through $w$.

Consider the following algorithm.

  1. Run Dijkstra on $G$ using $w$ as the source.
    Store $A[v] = \text{distance from } w \text{ to } v$.
     
  2. Reverse every edge of $G$ to obtain $G_r$.
     
  3. Run Dijkstra on $G_r$ using $w$ as the source.
    Store $B[v] = \text{distance from } w \text{ to } v \text{ in } G_r$.
     
  4. Return $B[s] + A[t]$.
     

Is the algorithm correct?

  1. Yes
     
  2. No

1 Answer

0 0 votes

The algorithm is correct, assuming we are looking for the shortest route from $s$ to $t$ that goes through $w$.

Any such route has two parts:

$s \rightarrow w$ and $w \rightarrow t$

So we need to find

$\text{dist}(s,w) + \text{dist}(w,t)$

First, run Dijkstra from $w$ in the original graph $G$.

This gives the shortest distance from $w$ to every vertex. Therefore,

$A[t] = \text{dist}(w,t)$

The problem is that we still need $\text{dist}(s,w)$, but Dijkstra starting at $w$ does not give distances to $w$.

So we reverse every edge of the graph.

In the reversed graph, a path $s \rightarrow w$ in $G$ becomes $w \rightarrow s$ in $G_r$ with the same total weight.

Therefore, running Dijkstra from $w$ in $G_r$ gives $B[s] = \text{dist}(s,w)$ in the original graph.

Hence,

$B[s] + A[t] = \text{dist}(s,w) + \text{dist}(w,t)$

which is the required shortest distance through $w$.

Since all edge weights are positive, Dijkstra's algorithm can be used in both runs.


Answer: Yes

Answer:
Position:
Show:

Related questions

2 2 votes
1 1 answer
101
101 views
GO Classes asked Aug 26
101 views
What is the primary reason to use Floyd's algorithm for the all-pairs shortest-path problem instead of Dijkstra's algorithm?Faster for dense graphs. Faster for sparse gra...
1 1 vote
1 1 answer
122
122 views
GO Classes asked Aug 26
122 views
Let, $G=(V,E)$ be a connected undirected graph. Edge weights may be negative.We want to choose, $E'\subseteq E$ such that $G'=(V,E')$ is connected and: $\sum_{e\in E'}w(e...
0 0 votes
1 1 answer
152
152 views
GO Classes asked Aug 26
152 views
Which of the following cannot be a sequence of keys compared during a binary search for some target key?$500,200,450,180$ $500,450,200,180$ $180,500,200,450$ $180,200,500...
0 0 votes
1 1 answer
88
88 views
GO Classes asked Aug 26
88 views
Consider,f1(N): x = 0 for i = 0 to N - 1: x++ return xand,f2(N, R): x = 0 for i = 0 to N - 1: for j = 1; j <= R; j = j + j: x = x + f1(j) return xWhat is the order of gro...