Shortest path between two points of a graph

Shortest path between two points of a graph

[helder da silva]

Algorithms, Graphs :

I found how to calculate the shortest path between two points of a graph,
http://www.ee.uwa.edu.au/~plsd210/ds/dijkstra.html

but how to know which points exactly the path goes through ?

Re: Shortest path between two points of a graph

[Larry Kilgallen]

In article <87qddp$t13$1@bw107zhb.bluewin.ch>, "helder da silva" <pc-tech@bluewin.ch> writes:
> Algorithms, Graphs :
> 
> I found how to calculate the shortest path between two points of a graph,
> http://www.ee.uwa.edu.au/~plsd210/ds/dijkstra.html
> 
> but how to know which points exactly the path goes through ?

You do it by using mathematics, which would be covered somewhere other
that the Ada newsgroup.

Re: Shortest path between two points of a graph

[Ted Dennison]

In article <87qddp$t13$1@bw107zhb.bluewin.ch>,
  "helder da silva" <pc-tech@bluewin.ch> wrote:
> Algorithms, Graphs :
>
> I found how to calculate the shortest path between two points of a
graph,
> http://www.ee.uwa.edu.au/~plsd210/ds/dijkstra.html
>
> but how to know which points exactly the path goes through ?

I suspect that algorithm finds exactly that. Otherwise its just telling
you that there *is* a shortest path, which is equivalent to finding if
there is *any* path, in which case I suspect Dijkstra would have billed
it as such. He's a pretty smart guy. :-)

If this is an assignment for a class, I'd highly suggest talking this
over with your instructor. That's what you're paying them for. Either
way, this is an algorithm question, not an Ada question.

--
T.E.D.

http://www.telepath.com/~dennison/Ted/TED.html


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Shortest path between two points of a graph

[G]

ASSET_A_230

If you can find that file on asset.com, you will find implementations in
Ada95 of the
algorithm in 2 and 3-dimensional spaces.


-G.