| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
I have a network of n points. The pathes between these points
are not neccessary bi-directional.
Example:
1 <----------> 2 <-----+
| | |
| | v
|+--------------+ 3
|| ^
vv |
4 ------------> 5 <-----+
I defined now a matrix which represents the network connections
and because I have one-way and two-way connections I used
the following matrix M
To:
0 1 0 1 0
1 0 1 1 1
Connection from: 0 1 0 0 1
1 0 0 0 1
0 1 1 0 0
As for an example, to go from point 1 to 5, you can
go from 1 to 2 and from 2 to 5.
From 5 to 1 you can go from 5 to 2 and 2 to 1, but not
from 5 to 4 and than 1, because 5 cannot go to 4 only
the other way around.
Now I want to be able to find a path between two given
points. The algorithms I have in mind do only support
networks with only bi-directional ways, not the one
I have.
Can someone tell me how I can find the ways in such a
network, or give me a pointer to a good book which deals
with problems like this.
Thanks,
Julian.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 679.1 | Hope I can help | SEMI::NG | Sun Mar 22 1987 01:54 | 19 | |
I'm not sure whether I would answer your problem correctly.
Couldn't you use any of the shortest path algorithms, like Dijkstra's
algorithm, with the cost between all vertices, if exist, to 1.
If you are interested in finding all-pairs paths, you could use
Floyd's algorithm. If you are interested in finding out just whether
this is a path between any 2 vertices, you could use Warshall's
algorithm to find the transitive closure.
I think these are all fairly standard algorithms. I think you could
find them in any graph theory books that talk about shortest-path
algorithms. There is a small section in
Aho, Hopcroft & Ullman, Data Structures and Algorithms
where I got these information from.
Hope I help you. I suspense there are other ways without using finding
the shortest path.
David
| |||||
| 679.2 | Shortest path programs | DENTON::AMARTIN | Alan H. Martin | Sun Mar 22 1987 12:53 | 21 |
I don't see why Dijkstra's algorithm (among others) wouldn't work. Two implementations of Dijkstra's algorithm for undirected graphs are SHORT.ADA and SHORT.C in TLE""::UPORT$:[AMARTIN]. (Another is SHORT.B36 on TLE""::UPORT$:[AMARTIN.VINO] and I've got one written in Rutgers Pascal, probably on the TOPS20 cluster). I wrote the Pascal version first, and then transformed it into Bliss-36. The Bliss-36 was transformed into C and the C was transformed into Ada. The programs assume that they are reading an undirected graph, but they represent the graph as a digraph where any edge from vertex p to q is matched by a vertex from q to p. It would be trivial to modify them to simply not add the back edge when reading a graph. And I believe that they would still work correctly on the resulting digraphs, even if they were not even weakly connected. However, I never tried to verify this. A description of the distances between over 900 points in the Catskill, Central and Adirondack regions of New York state is in [AMARTIN]NY. on the above designated disk structure. /AHM | |||||
| 679.3 | Thanks. | ANYWAY::WOLFF | I feel the need, the need for speed | Mon Mar 23 1987 12:00 | 7 |
Thanks, for your answers, I found a solution over the weekend,
I will use Dijkstra's algorithm combined with Warshall to get
what I need.
Julian.
| |||||