Dijkstra Algorithm
Hi all,
I have adjancy matrix for the graph in n x n dimension. where n is the number of node.
As Example,
Suppose i have 5 nodes called a,b,c,d & e
where edges are as under :
a->e
a->b
d->e
d->c
e->a
e->c
Then my matrix would be like
0,0,0,0,1
0,1,0,0,0
0,0,0,0,0
0,0,1,0,1
1,0,1,0,0
where i represents connectivity from 1 node to other node.
I want to generate distance matrix from this matrix using Dijkstra theory. Where i need minimum distance between two nodes, here distance means number of vertices to be visited. Distance matrix would be also n X n dimenion but values are representating vertices to be visited to reach i node to j node.
Can anybody please provide me code for this algorithm ? Or any idea how to achieved this ?
Thanks in advnace,
Dimple
Sorry matrix would be like :0,1,0,0,10,0,0,0,00,0,0,0,00,0,1,0,11,0,1,0,0
Dijkstra's algorithm finds the shortest path in a "weighted" graph, right? Seems your edges are not wieghted at all (no length), or am I missing something?
If you stop learning, you stop living!Tell us what you have done so far and where your current solution fail.
parza at 2007-7-13 8:32:00 >
> Dijkstra's algorithm finds the shortest path in a
> "weighted" graph, right? Seems your edges are not
> wieghted at all (no length), or am I missing
> something?
Sorry, didn't read your question with enough attention... Sorry, I just read that the shortest path is the least number of vertexes to travel.
So going from d to c could result in the following paths:
[ d -> e -> a -> e -> c ]
[ d -> e -> c ]
[ d -> c ]
where the last one obviously is the shortest, right?
Seems like a regular "breadth first search" can be implemented here. Have you tried programming this? Or something else to solve your problem?
The Floyd algorithm would be the best approach for this. It takes as input the nxn adjacency matrix as input and transforms it into the nxn shortest path matrix.
I didn't try BFS, but i don't think here it would be work out. My real data having 200 X 200 array, so it would be increase the complexcity. Floyds or Djkstra Algorithm can be work out.
My main aim to put quesition at forum is i need to get idea to decrease performance time.
If any body have any other idea, like whenever i am putting any node or edges i can maintain neigbour nodes and edges or anything like that which will increase the performace.
> I didn't try BFS, but i don't think here it would be
> work out. My real data having 200 X 200 array, so it
> would be increase the complexcity. Floyds or Djkstra
> Algorithm can be work out.
Dijkstra's shortest path algorithm *is* a breadth first search. The only
difference is that the 'front' of the search space is kept sorted on
distance travelled so far, i.e. it always picks the shortest partial
path first for expansion.
If your graph has a Euclidean space property, i.e. the algebraic
distance (number of edges in the path) more or less coincides
with the Euclidean distance, another heuristic can be used:
instead of keeping the search space sorted on distance, sort it
on distance plus the Euclidean distance from that point to the
target point. For, say, road networks this heuristic does wonders.
kind regards,
Jos
There are no Euclidean space in graph. If possible provide some sample code for both of these algorithm.
I think this has got to the point that you need to be told to do your own homework. If you write code which doesn't work, come back and you'll probably get help to debug it, but laziness is not something which most forum regulars wish to promote.
> My real data having 200 X 200 array, so it
> would be increase the complexcity. Floyds or Djkstra
> Algorithm can be work out.
About 9 years ago I used Floyd to obtain a feasible solution starting point for a non-linear optimization of a 640 node (640 x 640 matrix) telephone network. I used C++ and ran it on some old Sun box. The Floyd part took less than 3 seconds. Using Moore's 18 months law (http://en.wikipedia.org/wiki/Moore's_law), I bet that this would now take less than 3 / 2^6 seconds i.e. 1/20 seconds.
Even using the 2 year version of Moore's law it would take less than 3 / 2 ^ 4 seconds i.e. 0.2 seconds.
I went through that link, but didn't got algorithm. Can you provide me psudocode ? We are running out of time so if any body provide me code then it would be appriciated.Thanks in advance,Dimple
Try Google for "Floyd" and "pseudocode". I get almost 10.000 hits.
