-
June 9th, 2005, 01:06 PM
#1
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.
-
June 14th, 2005, 01:35 AM
#2
Re: shotest path between two vertices in a graph
What do you mean by "between 2 vertices... through minimum number of vertices" I don't understand what you mean by this.
Mike
-
June 30th, 2005, 02:22 PM
#3
Re: shotest path between two vertices in a graph
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.
-
June 30th, 2005, 05:30 PM
#4
Re: shotest path between two vertices in a graph
You need the help of Djikstra's algorithm:
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Power Macintosh G4/500 PCI
OS X 10.5.4 • 1024MB RAM • 120GB x 3 • Pioneer DVR-111D CD-RW/DVD-RW • Radeon 7000 PCI x 2, dual 17" Displays
http://www.jeffhoppe.com
-
July 3rd, 2005, 11:20 AM
#5
Re: shotest path between two vertices in a graph
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.
-
July 3rd, 2005, 12:10 PM
#6
Re: shotest path between two vertices in a graph
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)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|