Shortest Path Problem using VBA

[giorgiolocatelli]

Hello!

Can someone help me to develop this problem?

Dynamic Program Implementation using a MS Excel VBA program language. Implementation should be capable of solve distinct instances showing the solution found and its value.

The problem is:

"Determine the shortest path between two points. To connect the two points must pass through intermediate points."

Here is the image of the problem:

Diagrama Gráfico.jpg

Thank you!

[Marc L]

Hi !

As per forum rules, we do not achieve any homework without seeing any logic / algorithm well explained …

[giorgiolocatelli]

We useDijkstra's algorithm

For the first iteration, the current intersection will be the starting point, and the distance to it (the intersection's label) will be zero. For subsequent iterations (after the first), the current intersection will be a closest unvisited intersection to the starting point (this will be easy to find).

From the current intersection, update the distance to every unvisited intersection that is directly connected to it. This is done by determining the sum of the distance between an unvisited intersection and the value of the current intersection and then relabeling the unvisited intersection with this value (the sum) if it is less than the unvisited intersection's current value. In effect, the intersection is relabeled if the path to it through the current intersection is shorter than the previously known paths. To facilitate shortest path identification, in pencil, mark the road with an arrow pointing to the relabeled intersection if you label/relabel it, and erase all others pointing to it. After you have updated the distances to each neighboring intersection, mark the current intersection as visited and select an unvisited intersection with minimal distance (from the starting point) – or the lowest label—as the current intersection. Intersections marked as visited are labeled with the shortest path from the starting point to it and will not be revisited or returned to.

Continue this process of updating the neighboring intersections with the shortest distances, marking the current intersection as visited, and moving onto a closest unvisited intersection until you have marked the destination as visited. Once you have marked the destination as visited (as is the case with any visited intersection), you have determined the shortest path to it from the starting point