CODEWITHSUNDEEP
graphshortest-path
pnk6
pnk6

Reputation: 328

Verify the shortest path of a graph

[Edited] For a graph G, we are given the shortest path distances from a vertex V1 to every other vertex of the graph. How can we verify that the distance given are the actual shortest paths that one can find (by Dijkstra's or some other algorithm)? and its running time?

Upvotes: 2

Views: 3815

Answers (3)

Thomas
Thomas

Reputation: 1090

I assume your graph is directed (undirected case works similar). For every edge (u,v) you have to verify that dist(v) <= dist(u) + length(u,v) holds. Moreover, for every vertex v, you need an edge (u,v) such that dist(v) = dist(u) + length(u,v). This can obviously be done in O(m) time, which is faster than just applying another shortest path computation. Moreover, it is less likely to have bugs.

Upvotes: 6

Cemron
Cemron

Reputation: 1491

[EDIT] How about running dijkstra's algorithm (which calculates the shortest path distances) and comparing it to the given distance?

The running time? Which running time is meant? Of the algorithm? The internet should give you enough information about that.

Hope I served what you wanted.

Upvotes: -2

popo joe
popo joe

Reputation: 910

the question is not clear, do you want to lknow how to find the shortest path? in that case i'd suggest that you look into Dijkstra

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

and A* algorithm, A* is quite easy to implement.

http://en.wikipedia.org/wiki/A*_search_algorithm

Upvotes: -2

Related Questions