B4J Code Snippet [B4X] Dijkstra's Algorithm for Finding the Shortest Path Through a Connected Graph.

A connected graph is a series of nodes connected with edges.
The edges have a weight (in this example I use 1 for all edges - but any weight will do)

Dijkstra, a Dutch computer scientist thought this up in 20 minutes while out for a cup of coffee.
It was a mental exercise, he says.

It is best understood in reverse.

Consider the nodes with edges going into the target.
"Assume" we know the shortest path to each of those nodes.
Then we can add the corresponding edge weights and take the minimum of those sums.
That would be the shortest path to the target. The node corresponding to the minimum would be on the path.
If we don't know the shortest path to a given node, consider that node the target and repeat the process!

The actual algorithm goes forward by computing the shortest path to all nodes starting with the source.
This algorithm is famous and has been implemented in many computer languages. This is my contribution to B4X.

I have attached the source code with some extras to create various test graphs in B4J.
In the B4A version these extras are not used.

It is fast for small graphs, but time varies rougly as n squared where n is the number of nodes.
For the graph above, it took 35 MICROseconds to complete (I ran it 1000 times to get a total of 35 miliseconds)
On the Android device, it ran about 8x slower.

I searched the B4X Forum, but I couldn't find a source code. It may be as part of Library, I don't know.
The algorithm has wide application in finding the shortest route through various terrains with obstacles.

Private Sub solveDijkstra
    sourceNode.distanceFromSource = 0
    sourceNode.visited = True
    Dim notDone As List: notDone.Initialize
    For i = 0 To nodes.Size - 1
        notDone.Add(i)
    Next
    Do While notDone.Size > 0
        Dim minx As Int = minIndex(notDone)
        Dim currentNode As CNode = nodes.Get(notDone.Get(minx))
        Dim ID As Int = currentNode.ID
        For Each neighbour As CNeighbour In currentNode.neighbours
            Dim tempDistance As Int = currentNode.DistanceFromSource + neighbour.weight
            If neighbour.nd.visited = False And tempDistance < neighbour.nd.distanceFromSource Then
                neighbour.nd.distanceFromSource = tempDistance
                neighbour.nd.previousID = ID
            End If
        Next
        currentNode.visited = True
        notDone.RemoveAt(minx)
    Loop
End Sub

Private Sub minIndex(notDone As List) As Int
    Dim minDist As Int = UNKNOWN
    Dim minx As Int
    For i = 0 To notDone.Size - 1
        Dim nd As CNode = nodes.Get(notDone.Get(i))
        If nd.distanceFromSource < minDist Then
            minDist = nd.distanceFromSource
            minx = i
        End If
    Next
    Return minx
End Sub

 

[aeric]

Similar to Minimum Spanning Tree?

https://b4x.com:51041/mst/index.html

 

[William Lancee]

@aeric

Similar but not the same, a minimal spanning tree is the shortest path that visits each point at least once.
The algorithm @Erel used is the Prim's algorithm, actually an earlier invention than Dijkstra's.

In Dijkstra's case, there are nodes that don't need to be part of the shortest path that goes from source to target.

 

[William Lancee]

There are newer algorithms than Dijkstra's, but not as popular.

One interesting one is to copy ants' behaviour in finding food.
They do this by applying an external memory based on pheromones and following paths found by other ants.
This approach is called Ant Colony Optimization

 

[aeric]

What do you want to accomplish with this algorithm?

A few days ago, I saw a video on a competition where the robot find the shortest path inside a maze. Maybe this can be use.

 

[kimstudio]

Quite useful for certain games programming...

 

[William Lancee]

It can be used in any situation where you can transform some terrain or building layout to a graph of nodes which could be
landmarks or hallway intersections. The weights on the edges could be distances between landmarks.

Then to get instructions to go from one landmark to another some distance away, the shortest path would lead you there.

For example

https://www.b4x.com/android/forum/t...igation-system-for-a-complex-facility.148847/

 

[William Lancee]

For my own testing purposes I built in a rudimentary graph designer.
To use it (in B4J) you need to know the steps.

Step 1. Set inDesign to True
Step 2. Run and place nodes on the screen with mouse clicks
Step 3. After all nodes are laid down click on the GREY button on the side
Step 4. Click roughly on the middle between two nodes to create an edge between them
Step 5. Click on the RED button to select the node that will be the source - click a node to mark it as the source
Step 6. Click on the GREEN button to select the node that will be the target - click a node to mark it as the target
Step 7. Click on the OPEN lowest circle to show the graph definition in the logs
Step 8. Copy the log to the 'getModel' sub - you'll see where - replace what's there or just add it below in a overriding string
Step 9. Set inDesign to False and run

As I said, this isn't part of the demo, so you only need to know this to set up test data.
It was created like this for me and was done in about 15 minutes. So it is pretty ugly, but it works.
Since I know the steps I can create a new graph in a few minutes.

[Note: ignore the blue button]

 

[aeric]

It can be used in any situation where you can transform some terrain or building layout to a graph of nodes which could be
landmarks or hallway intersections. The weights on the edges could be distances between landmarks.

Then to get instructions to go from one landmark to another some distance away, the shortest path would lead you there.

For example

https://www.b4x.com/android/forum/t...igation-system-for-a-complex-facility.148847/

Nice.
I have an appointment for clinic later.
My arm was bitten by a poisonous insect.
Hope I don't lose my way there. ?

 

[derez]

There are examples of coded algorithm in the forum for A* , or A-star (one is mine...)
I googled and saw this:

A* algorithm is just like Dijkstra's algorithm, and the only difference is that A* tries to look for a better path by using a heuristic function, which gives priority to nodes that are supposed to be better than others while Dijkstra's just explore all possible ways.

 

[TILogistic]

There are examples of coded algorithm in the forum for A* , or A-star (one is mine...)
I googled and saw this:

I saw this post years ago when I was looking for short path algorithms.

A* (Astar) Library (B4J also)

This library can be used to find the shortest route between two point in a net of nodes (like a matrix in a game or net of roads). The library needs a public sub in the calling module named [Eventname]_Neighbors(x As Double, y As Double) As List This sub should provide a list of all neighbor...

www.b4x.com

A* search algorithm - Wikipedia

en.wikipedia.org

 

[William Lancee]

@derez

I did search for and find A* as part of the excellent @Informatix "Steering" library. But it is not free (and shouldn't be) and it is not open sourced.
I did find your submission, but it seemed unfinished and as far as I could tell you ended up with the algorithm from @Informatix.

While I am familiar with A*, it requires a heuristic. If there is a heuristic, A* is faster than Dijkstra. An example of a heuristic would be the distance as the crow flies - (like google maps). The situation I was thinking of had no such heuristic. You can can put a dummy heuristic in A*, but then it becomes like Dijkstra's but more complicated

Dijkstra's method is compact and easy to understand and fast enough for moderate sized graphs, and it is a classic.
As I mentioned, there are newer algorithms, for example Ant Colony Optimization.

You can stop reading now!

We have an ant problem in our patio, and I am fascinated by how they work. So I am experimenting to see how fast the algorithm is.
I suspect it will be faster for a large graph and possible slower for a small graph.

I first came across Dijkstra's solution in 1969 when I was specializing in combinatorics and optimization at the U of Waterloo.
It seemed perfect for a recursive formulation but that turned to be very difficult (anyone out there want to give it a try?)
Since then I moved on to other things, so it was only in the past week when I came across it again - see link in #7.

As a completely irrelevant fact, I was born in Eindhoven (Netherlands) and when Dijkstra was devising this algorithm in Amsterdam,
I was bicycling with my older cousin from Eindhoven (South) to Drente (North), a route of hundreds of sections of bicycle paths.
Did we choose the shortest route? It was a two-day trip with a sleep-over in Swolle (about halfway).
The first day was probably the shortest path (at least by visual inspection of the map).
The second day was very complicated with rivers and other obstacles, so we'll never know.
And when you're having fun, maybe shortest and fastest isn't optimal.

 

[William Lancee]

I have added a little guidance to the graph designer.
Slightly modified version in #1. Algorithm is the same.

 

[derez]

@derez

I did search for and find A* as part of the excellent @Informatix "Steering" library. But it is not free (and shouldn't be) and it is not open sourced.
I did find your submission, but it seemed unfinished and as far as I could tell you ended up with the algorithm from @Informatix.

While I am familiar with A*, it requires a heuristic. If there is a heuristic, A* is faster than Dijkstra. An example of a heuristic would be the distance as the crow flies - (like google maps). The situation I was thinking of had no such heuristic. You can can put a dummy heuristic in A*, but then it becomes like Dijkstra's but more complicated

Dijkstra's method is compact and easy to understand and fast enough for moderate sized graphs, and it is a classic.
As I mentioned, there are newer algorithms, for example Ant Colony Optimization.

I did not mean to insult you or Dijksra, just mentioned the availability of A* in the forum.
I did not use Informatix 's algorithm. When I first published it and found about his solution which is charged for, Informatix said that he does not object to my publishing as it is different .
See these posts : https://www.b4x.com/android/forum/threads/a-astar-library-b4j-also.48825/post-304247 , https://www.b4x.com/android/forum/threads/a-astar-library-b4j-also.48825/post-316523

 

[William Lancee]

@derez

Neither me nor Dijkstra are remotely offended.
I'm sorry, but I misread your post (especially the last posting).

Would you share your source code for A*? I would be very interested.

 

[emexes]

The situation I was thinking of had no such heuristic.

Can you give a clue as to that situation? Heuristic still works in 3d, although I agree it would be less-effective in eg buildings where the vertical and horizontal travel costs are asymmetric.

Dijkstra's method is compact and easy to understand and fast enough for moderate sized graphs

As with the Travelling Salesperson Problem, real situations don't restrain themselves to being moderate sized. I wrote a routing program for when I was doing delivery driving, typically 60-80 stops per day, and the practical limit for a full exhaustive search was about 20 stops (= 20! = 2.4 million trillion possible paths).

 

[emexes]

I wrote a routing program

I vaguely remember that I posted some mazes here generated by that algorithm. It would make x-thousand random points (stops) and then find a shortish (not shortest) path that visited each point once.

edit:

https://www.b4x.com/android/forum/threads/kids-vs-travelling-salespeople.136017/#post-860245

https://www.b4x.com/android/forum/threads/route-between-points-google-maps.143987/#post-912868

but this is digressing from the original challenge of finding the shortest path from A to B, other than as a demonstration that heuristics are often useful for routing.

 

[William Lancee]

@emexes Can you give a clue as to that situation?

Navigating a complex facility.

https://www.b4x.com/android/forum/t...igation-system-for-a-complex-facility.148847/

@emexes As with the Travelling Salesperson Problem, real situations don't restrain themselves to being moderate sized.

The Travelling Salesperson Problem has greater complexity than the shortest path (n! vs n squared)

In a building complex the problem can be subdivided into graphs at 3 levels: buildings as nodes, floors as nodes, major locations as landmarks.
The target node is defined as the access point to the next level, and finally the target location of the full route.
If a given graph has 50 nodes, less then 50x50 = 2500 steps, then this algorithm could find the shortest path in less than 1 second on a Android tablet.

 

[PABLO2013]

muchas gracias por tu aporte valioso y tu tiempo.