Minimum route from two nodes
 

What is the algorithm to find the minimum route from two nodes of a
undirected graph

--
stefante
-----------------------------------------------------------------------
stefantem's Profile: http://www.excelforum.com/member.php...fo&userid=1359
View this thread: http://www.excelforum.com/showthread.php?threadid=26312

Minimum route from two nodes
 

What is an undirected graph? I don't recall this from my
maths days ...

Rgds

Rog



-----Original Message-----

What is the algorithm to find the minimum route from two
nodes of an
undirected graph?


--
stefantem
----------------------------------------------------------
--------------
stefantem's Profile: http://www.excelforum.com/member.php?
action=getinfo&userid=13594
View this thread:
http://www.excelforum.com/showthread...hreadid=263127

.

Minimum route from two nodes
 

stefantem wrote in message ...
What is the algorithm to find the minimum route from two nodes of an
undirected graph?
Stefantem,

Don't know if this would help, but I had to find something similar.
My problem was lots of line segments with many nodes. The only thing I
had to work with was the (x,y) coordinates of each line segment. For
example, line 1 was described as (1,1),(4,5). Therefore, a line can be
drawn from (1,1) to (4,5). The second line would be connected to the
first and would be described as follows, (4,5),(10,15). And so. There
would be points in the path where more than one line is attached and
would branch from that node. Eventually a path would just end.

In short, I built an Excel program that did what I wanted the brute
force way.
1) Find all starting nodes (nodes are the (x,y) point of a line that
is not connected to another line segment).
2) Using the line segment that has the starting node (x,y) coordinate,
start finding and connecting those segments together.
3) Keep connecting line segments until no more can be connected.
4) Keep track of nodes with multiple paths, you will have to
back-track to those nodes and make new paths.
5) Repeat the above with all the identified starting nodes.
6) Once finished you have all the possible paths.
7) Sort to find the two nodes that are connected. One should be at the
beginning of the path, the second should be at the end of the path.
8) Calculate the length of each line segment used to create the path,
i.e. (x,y) coordinates of each line, length = sqrt((x2-x1)^2 +
(y2-y1)^2)
9) Add of the lengths, the short value will be the shortest path.

Hopes this helps.

RichardG