Route Planning - shortest path

[Robrobby]

I'm trying to get my head around using the following data to create the shortest route between 2 places in a map using VBA in either excel or access.

ID	Name	Connection 1	Connection 2
1	Location1	2
2	Location2	3	4
3	Location3	2
4	Location4	2	5
5	Location5	3	5

So if my start location was Location3, how would I plan a route to get to location1
I expect it would be better to have the data in the following format:

ID, Connection
1, 2
2, 3
2, 4
3, 2
4, 2
4, 5
5, 3
5, 5

The result in this instance would have to be 3->2, 2>1
But how do I get that result.
In the real data there is over 300 locations, some with up to 20 connections each.

Anyone have any suggestions on where to start?

 

[jdraw]

Google "shortest path problem" for a starting point.

Here's a shortest path example in Excel (couldn't find one quickly in Access/vba)
Another link that may be relevant.

Note: MajP on this forum is very experienced with math-oriented programming and often responds with samples/solutions.

Good luck. Let us know if you find a solution.

OOoops: I see he has already responded while I was composing

 

[MajP]

After rereading this it does not look like a TSP, you do not want to visit all nodes. You want to find a path through the graph from one point to another.
If you want to find the shorted path this is solved using Dijkstras algorithm.

Dijkstra's algorithm - Wikipedia

en.wikipedia.org

Basically this method used Dynamic Programming where you record at each node the best route to get to that node. Then build off of that. You can find lots of vba examples.

If you want all the possible paths it is done in a similar manner, but just span the entire graph and end up at the destination node. Do you want the shortest (you would need some distance between nodes), a single path, or all possible paths?

Any chance you can post some real data so we can see the format? I will see if I can code a solution for shortest or all paths.

 

[MajP]

Although the OP no longer seems interested, but in case someone is. I did a demo of the Dijkstra algorithm for finding shortest path through a graph. Here is a simple version using just arrays.

User:Klever

.

rosettacode.org

I like to use more complicated data structures because it makes importing table information in and exporting results out to the db easier.

 

[namliam]

I hope these numbers are random, they dont seem to make sence.

How about adding a component time as well? I can see a,b,c beeing 40 and a,c beeing 50. Time wize it should probably be reversed.
Routing on distance isnt the key I think as you will always arrive at a,b,c even if b isnt needed ?

 

[MajP]

I hope these numbers are random, they dont seem to make sence.
How about adding a component time as well? I can see a,b,c beeing 40 and a,c beeing 50. Time wize it should probably be reversed.
Routing on distance isnt the key I think as you will always arrive at a,b,c even if b isnt needed ?

@namliam
In graph theory you have Vertices (nodes) and Edges the connections between the Vertices. Sorry, I used the term Distance to be less confusing, but the more general term is Cost. Where the cost is the resources to move from a Vertex to another Vertex (Time, days, money, personnel required, ingredients, distance, cpu useage, fuel consumed, electricity required, lines of code etc.) In the above graph the Vertices could represent manufacturing tasks and the Edge Costs could represent days or personnel required to move to the next task. So the "Distance" field really should be a generic "Cost" field so if could be populated as is with time data. So nothing is random, not sure what you mean by that.

I think as you will always arrive at a,b,c even if b isnt needed ?

Again this is shortest path. Yes, there is another ways to get A->C but the cost is greater.
A,B,C,D: 40
A,C : 50

In the Example shown A->D
A,B,C,D = 60
A,C,D : 70
A,D: 65

 

[namliam]

What I mean with random is assuming it is distance you can make nice triangles however these triangles do not add up.
B, D, E 70, 23, 4 cannot happen in distances assuming this is a real world example in i.e. km distance.

ABDC may get you to C however the arrow doesnt support said route though can be my stupid singular direction brain that is limitting this option.

 

[MajP]

@namliam

What I mean with random is assuming it is distance you can make nice triangles however these triangles do not add up.
B, D, E 70, 23, 4 cannot happen in distances assuming this is a real world example in i.e. km distance.

Since you mention triangles, I have to assume you are assuming that the picture is a cartesian plane and that distances are euclidean.
sqrt((x2-x1)^2 + (y2-y1)^2). Although this is possible, in real life this is a small subset. Even if this represented locations on a map, the distances walking or driving is rarely euclidean. If this is a city, it would only be euclidean if you had a helicopter and allowed to travel directly from A to B. In real life you have winding roads, detours, oneway streets. Often the route from A to B is not the same distance of B to A. Think a city with one way roads. Or think these are locations in a national Park. As the bird flys the distance from A to B may be short but you have to follow the trail which goes around the lake, bypasses the gulch, and switches back and forth across the mountain.

ABDC may get you to C however the arrow doesnt support said route though can be my stupid singular direction brain that is limitting this option

I think you are trying to limit it to a very specific example. As said the graph is a generic representation not a cartesian map.
More Graph Theory
-Un-Directed Graph: Cost from A to B is the same from B to A, and you can traverse in either direction: A---B
-Directed Graph: Cost From A to B is different than B to A, or you can only go in one direction. A--->B or A<---B or able to go in both directions but different costs per direction (cannot draw that but two arrows with different cost in each direction)
-Connected Graph: You can get to any point from any other point. There exists a path. There are no disconnected branches (islands)
-Fully Connected Graph: This is graph where every point connects to every vertex connects to every other vertex.
The pictured graph is a Directed, Connected graph and not fully connected. So

ABDC may get you to C however the arrow doesnt support said route

that is correct. Imagine this is a train system which is also not a fully connected graph, you cannot get to every station direct from every other station. If this was a fully connected, euclidean graph the solution is trivial. The shortest path from A to C is A,C.

 

[Robrobby]

Thanks everyone for looking into this. I've been looking at the Dijkstras algorithm myself but as you said, I basically want to enter a start location and a destination and find the shortest path between the two. The attached file has a list of all the nodes that I'm working with.

 

[MajP]

I put this into my model and works except, I have to do some updates because you have a disconnected graph and I do not account for that.
For example node 187 can be entered from 202, but 187 goes to nowhere. It has no other connection.

 

[MajP]

This appears to work, need you to verify the results.

 

[MajP]

I ran my code against all possible paths ~125k. Could not upload the whole thing so the remaining solutions are in the Excel files. You will have to import them.
I did this brute force and looped Dijkstra because I was to lazy to code a Floyd Warshall algorithm which is a way to find all the shortest paths. Ran over night. Take a look. I get what I believe to be disconnected nodes, but you may want to verify the results.

 

[Robrobby]

Wow, that's some work you've put in there, Many thanks. Now I’ve got the backbone of it all I can start building on this. Will be good to start re learning access.

 

[Robrobby]

I ran my code against all possible paths ~125k. Could not upload the whole thing so the remaining solutions are in the Excel files. You will have to import them.
I did this brute force and looped Dijkstra because I was to lazy to code a Floyd Warshall algorithm which is a way to find all the shortest paths. Ran over night. Take a look. I get what I believe to be disconnected nodes, but you may want to verify the results.View attachment 79772

Looks like I need to do some cleaning up. Your results will help me a lot. 125k results, wow. This is why I ask the experts.

 

[MajP]

I am working on a version of the FloydWarshall algorithm. I will post when done.

 

[MajP]

If @Robrobby or anyone is interested I coded the Floyd-Warshall algorithm that records the shortest path for every node in a directed graph to every other node. My version is heavy on custom classes. However the link in thread 4 shows an array based solution, which will be easier to develop if you are not versed in vba custom classes and advanced data structures. The classes make it easier to get the data in and out of the db.
The OPs problem has 365 nodes (vertices) which means a potential solution if fully connected could have up to ~130k nodes (n x n-1). I ran the solution and it was faster than calling the original single dijkstra 130k times. It still took hours.
I truncated the solution set so I can zip below 2meg to post.
If you want to run the solution (it will take hours) you need to rebuild tblAllPaths2 using the make table query. The button is on frmDijkstra2.

 

[Robrobby]

Thanks for all of your work so far, The amount of calculations this does it astounding.
On your form Dijkstra2 where I could enter the start/end I've linked the dropdown boxes to my own table of names so that I can select them, but I've been trying to get the resulting path into it's own table instead of the debug window so that I can add further notes, info, names etc.
I've never worked with Vba much in Access, only excel. Could you point me in the right direction please.

 

[MajP]

See if this is what you meant. Mostly what you are asking is just a query to join TblAllPaths2 with tblZones. However, I modified the code to write the path names instead of just the path IDs. Also you could migrate this to Excel pretty easily, but I would think this is easier to work in Access. However, it is just using access for import of the data and export of the results. The code could easily work in Excel.

TblAllPaths is truncated because I could not zip every possible node combination. But you could run the make table query to do this. So what I did was you can navigate by combos or the first subform. Then you can calculate the paths and path names. I ran a few. I did not code the Floyd-Warshall with these updates. So you can just manually do one at a time. If this makes sense I can update the Floyd-Warshall to update all records.

 

[Robrobby]

Thanks again for this, it's just what I need.
The make table query seems to break things, So I've left that alone. As you said, it's just as easy to build up as you go. which is fine with me.

 

[MajP]

Thanks again for this, it's just what I need.

What a let down. I figured you needed this algorithm to solve the shortest path for defeating Corona virus transmission, but based on the names it looks like you are trying to find the fastest way to win in the online game Everquest. So much for helping to save the world . I did the floyd-warshall solution if you need it, but I will have to set up a google drive if you want it. If you just need to check one at a time, you should be good. Thanks, this was good practice and interesting.