shotest path between two vertices in a graph

Hi,

I want to find the shotest path between two vertices in a graph, which travels through minimum number of vertices. Can you plz tell me the algorithms that I should learn to do this.

Best regards,
Chamal.

What do you mean by "between 2 vertices... through minimum number of vertices" I don't understand what you mean by this.

what kind of running time are you looking for?

if you don't mind n^k or something horrific like that you just write a recursive function to find all possible paths to that vertex.
make sure you don't get caught in some sort of infinite loop.

an upper bound on how large that answer is to find the minimum spanning tree for the graph. you sum up all the edges there and it can be no larger than that.

there are two methods to find the minimum spanning tree (prim and kruskal)
I like Kruskal:
to find the minimum spanning tree you keep adding the smallest edge available that does not create a cycle until all vertices are connected.

once you have that tree you can start ripping off branches that don't lead towards your destination and narrow your bounds any more.

tex23bm

however, if you need THE minimum between two edges I think you might be forced into some really inefficient algorithm. then again i'm not an expert, i just enjoy these types of problems.

You need the help of Djikstra's algorithm:

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

I must warn you that if there is and edge with negarive value in the graph then you can't use dijkstra's algorithm. In this case you must use Ford - Belman's algorithm.

Quote:

---

Originally Posted by chamalsl

I want to find the shotest path between two vertices in a graph, which travels through minimum number of vertices. Can you plz tell me the algorithms that I should learn to do this.

---

well,you wanted the shortest path between two specific vetices as Judas1012 mentioned you should use Djikstra algorithm but in its general way you can use Floyd algorithm for considering every two vertices.(of cource for positive values)

if you use Dijikstra algorithm with a binary heap its complexity is

• O(a+n)logn (a is the number of edges)

its pseudo code(by using a binary heap),

Code:

---

/* T is used for the traces so we could come back to find the vertices made the path
L is the path matrix
D is the array for keeping minimum values
H is used for making heap */
Function Djikstra(L(1..n^2),D[1..n],H[1..n],T[1..n])
FOR i=2 to n DO D[i]<---L[1,i]
C<---{2,3,..,n}
array D[1..n]
MakeHeap(H[1..n])
REPEAT n-2 times //Greedy Loop
        V<---Return&DeleteHeapHead(H)
        C<---C-{V}
        FOREACH w in C which is the adjacent of V Do
        IF D[w]<D[V]+L[V,w]
                PercolateHeap(H,W)
                T[w]<----V
RETURN D

---

and it should be clkear why its time is O(a+n)logn because we have n-2 times Return&DeleteHeapHead(H) which takes nlogn and PercolateHeap(H,W) is executed as the same as the number of edges which takes alogn so the result time is O(a+n)logn

if you use the usual form of Djikstra algorithm its time is O(n^2) so now you can analyze them

• if a<<n using a binary heap is much better
• if a~=n^2 using its normal form is more efficient

but about Floyd algorithm(all-pairs shortest path problem)
its time is O(n^3) of cource we can use Djikstra algorithm n times for doing the same thing Floyd algoritm does for us and like the above analyzation

• if a<<n use Djikstra algorithm n times---->O(n[(a+n)logn])
• if a~=n^2 use Floyd algorithm ----->O(n^3)