All Shortest Paths To A Given Vertex

Given a directed graph G=(V,E) and a weight function w : E - > R+ (only positive weights for edges in the graph) , I need to find all the shortest paths from every vertex v in V to a given vertex k.

I've thought about reversing the edges in the graph and then running Dijkstra's algorithm from the vertex k. I wonder whether a shortest path p from k to v1 is actually the shortest path from v1 to k in the original graph ( before reversing edges ).

I'd be grateful if anyone could explain if and why it does / does not happen.

Thanks in advance.

---

(This won't be the most formal proof in the world, but hopefully its good enough to convince yourself).

Lets say for a vertex v, in graph G, the shortest path from v to k is of length m. The two things you want to know are:
1. In the reversed graph, G*, there is a path of length m from k to v.
2. In the reversed graph, G*, there are no paths from k to v that are shorter than m.

Before I start, can we take one thing on faith:
Lemma 1: If you have a directed path from vertex v to vertex w, and you reverse every edge on the path, then you have a path from vertex w to vertex v. This is provable, but I think its fairly common sense. I'll prove it if you want me to.

For point 1: Consider the path in G from v to k consisting of m edges. If you reverse each of these edges, you will have a path from k to v of length m (by Lemma 1).

For point 2: Suppose there exists a path in the reversed graph G*, from k to v of length n < m. If you reverse this path, then there is a path of length n from v to k (Lemma 1). This means that there is a path from v to k in the original graph that is shorter than m, contradicting the statement that the path of length m is the shortest.

链接地址: http://www.djcxy.com/p/35282.html

上一篇: 在有向无环图中计算传入边

下一篇: 给定顶点的所有最短路径