Shortest Path between two vertices of a weighted, undirected graph IN LINEAR TIME

Question

Studying for an algorithms test, and a surprisingly simple problem has me somewhat stumped. The following is the question:

My issue has been - looking online, everyone uses this kind of problem to segway into talking about Dijkstra's algorithm. That's all fine and good, put Dijkstra I find to be a single-source algorithm that finds ALL shortest paths. That is powerful, but it also is not O(V+E).The runtime of Dijkstra's is, of course, O(V+E logV).

I'm trying to envision how one would do a "single run" of Dijkstra's, terminating at the target node, while GUARANTEEING the O(V+E) runtime. I have made an example in which I terminate Dijkstra's prematurely and it happened to look O(V+E)... but I don't know how I could really justify the correctness and analyze the running time truthfully - surely there is some graph where my algorithms runtime is poorer.

Answer 1

Use two stacks $S_0$, $s_1$ and a 2bit flag $f[v]$ per vertex

1. Set $f[v]=2$ for all $v\in V$,
2. Set $d\leftarrow 0$ and push $s$ to $S_0$
3. Pop $v$ from $S_0$
4. If $v=t$, output $d$ and terminate.
5. Set $f[v]\leftarrow 0$
6. For each edge $vu$, if $w(vu)<f[u]$, push $u$ to stack $S_{w(vu)}$ and set $f[u]=w(vu)$
7. If $S_0$ is empty, let $S_0\leftarrow S_1$, clear $S_1$, and let $d\leftarrow d+1$.
8. Goto 3

Step 1 take $O(|V|)$. Each vertex can be pushed to some stack at most twice (because each pushing decreases $f[v]$, except for the initial pushing of $s$). Therefore step 6 sees each edge at most four times (twice per endpoint). Thus the overall runtime is $O(|V|+|E|)$. For the validity note that $S_0$ and $S_1$ keep track of vertices at distance $d$ and $d+1$, respectively.

Answer 2

Use the hint- merge nodes that have weight 0 edges between them, then call bfs on the resulting graph. Merging nodes is linear in number of edges, while bfs is linear, as mentioned.