algorithm - All Shortest Paths To A Given Vertex -

given directed graph g=(v,e) , weight function w : e - > r+ (only positive weights edges in graph) , need find shortest paths every vertex v in v given vertex k.

i've thought reversing edges in graph , running dijkstra's algorithm vertex k. wonder whether shortest path p k v1 shortest path v1 k in original graph ( before reversing edges ).

i'd grateful if explain if , why / not happen.

thanks in advance.

(this won't formal proof in world, enough convince yourself).

lets vertex v, in graph g, shortest path v k of length m. 2 things want know are:
1. in reversed graph, g*, there path of length m k v.
2. in reversed graph, g*, there no paths k v shorter m.

before start, can take 1 thing on faith:
lemma 1: if have directed path vertex v vertex w, , reverse every edge on path, have path vertex w vertex v. provable, think common sense. i'll prove if want me to.

for point 1: consider path in g v k consisting of m edges. if reverse each of these edges, have path k v of length m (by lemma 1).

for point 2: suppose there exists path in reversed graph g*, k v of length n < m. if reverse path, there path of length n v k (lemma 1). means there path v k in original graph shorter m, contradicting statement path of length m shortest.