# 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.

B4X:
``````Private Sub solveDijkstra
sourceNode.distanceFromSource = 0
sourceNode.visited = True
Dim notDone As List: notDone.Initialize
For i = 0 To nodes.Size - 1
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``````

#### Attachments

• CGraph_V2.zip
18.1 KB · Views: 103
Last edited:

#### aeric

##### Expert
Longtime User
Similar to Minimum Spanning Tree?

#### William Lancee

##### Well-Known Member
Longtime User
@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.

Last edited:

#### William Lancee

##### Well-Known Member
Longtime User
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

##### Expert
Longtime User
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

##### Active Member
Longtime User
Quite useful for certain games programming...

#### William Lancee

##### Well-Known Member
Longtime User
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

##### Well-Known Member
Longtime User
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]

Last edited:

#### aeric

##### Expert
Longtime User
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

##### Expert
Longtime User
There are examples of coded algorithm in the forum for A* , or A-star (one is mine...)
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

##### Expert
Longtime User
There are examples of coded algorithm in the forum for A* , or A-star (one is mine...)
I saw this post years ago when I was looking for short path algorithms.

#### William Lancee

##### Well-Known Member
Longtime User
@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.

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

##### Well-Known Member
Longtime User
I have added a little guidance to the graph designer.
Slightly modified version in #1. Algorithm is the same.

#### derez

##### Expert
Longtime User
@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 .

Last edited:

#### William Lancee

##### Well-Known Member
Longtime User
@derez

Neither me nor Dijkstra are remotely offended.

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

#### emexes

##### Expert
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

##### Expert
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:

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.

Last edited:

#### William Lancee

##### Well-Known Member
Longtime User
@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.