Home |
Search |
Today's Posts |
#1
Posted to microsoft.public.excel.programming
|
|||
|
|||
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 |
#2
Posted to microsoft.public.excel.programming
|
|||
|
|||
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 . |
#3
Posted to microsoft.public.excel.programming
|
|||
|
|||
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 |
Reply |
Thread Tools | Search this Thread |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Forum | |||
Accessing macro from a system by all other nodes on LAN | Excel Discussion (Misc queries) | |||
how to delete duplicate file example route 2_2:1 or route 2_2:2 | Excel Discussion (Misc queries) | |||
XML selecting sinlge nodes with name selectionNamespaces | Excel Programming | |||
treeview add nodes | Excel Programming | |||
TreeView: add more than one node to nodes collection | Excel Programming |