Dijkstra's algorithm with VBA

[Worf]

Worf submitted a new Excel article:

Dijkstra's algorithm with VBA - Implements a shortest path algorithm for a 3D problem.

This article shows how to use Dijkstra's algorithm to solve the tridimensional problem stated below.

View attachment 2058

Dijkstra's algorithm - Wikipedia

• Actually, this is a generic solution where the speed inside the holes is a variable. The original problem is a particular case where this speed goes to infinity.
• Amelia, Otto and the holes are vertices; imaginary lines...

Read more about this Excel article...

 

[shg]

Nice work!

It appears (from the plot, didn't look at the code) that Amelia flies from hole center to hole center. It doesn't matter if the speed within the hole is infinite, but if not, she (is that her preferred pronoun?) could instead travel a shorter distance flying the chord of the sphere.

 

[Worf]

Hi shg

• Yes, Amelia is a she…
• I made some assumptions for this initial version, one of them is that the only allowed chords are the sphere diameters. When the edge connecting sphere A to sphere B goes through sphere C, it is not allowed. I am calling this visibility, A cannot see B.
• I wanted a graph where not all vertices were interconnected to every other vertex, like in the picture below. Visibility is the criterion to create the edges.
• The original problem fixes the two different speeds, but I made them variable.