16-Pearl

Question

Mathcad Community Challenge September 2025: Dijkstra's algorithm-Inspired Programming Challenge

Forum|Forum|7 months ago
September 1, 2025
9 replies
5600 views

This month’s challenge is a programming challenge inspired by Dijkstra’s algorithm, which finds the shortest path from a single source to all the other nodes in a network, based on weighting.

In this scenario, we will use points in a 2D plot, where the weighting is the distance between the points.

Djikstra Initial.png

Challenge 1: Known Points

For the provided points, write a program to calculate the shortest path from the first node (5,5) to all other nodes, always choosing the shortest path from the current node.

Feel free to use Mathcad's random number generator functions to make your own points instead. You can also start from a different point of your choosing if you so desire.

Challenge 2: Graphing

Create a Chart Component or XY Plot that graphs this path.

Challenge 3: Advanced Inputs

Incorporate advanced input controls to allow the user to change quantities such as the number of points or generate new points / path.

Challenge 4: 3D

Can you write a program that performs the same calculation, but for points in 3D instead of 2D?

A Mathcad Prime 10 worksheet that was used to generate the above image has been attached to this challenge.

Find the Mathcad Community Challenge Guidelines here! Have fun!

1_Dijkstra-Sample.zip

Puzzles Games

W

Werner_E

25-Diamond I

@DaveMartin wrote:

This month’s challenge is a programming challenge inspired by Djikstra’s algorithm, which finds the shortest path from a single source to all the other nodes in a network, based on weighting.

In this scenario, we will use points in a 2D plot, where the weighting is the distance between the points.

Challenge 1: Known Points

For the provided points, write a program to calculate the shortest path from the first node (5,5) to all other nodes, always choosing the shortest path from the current node.

Feel free to use Mathcad's random number generator functions to make your own points instead. You can also start from a different point of your choosing if you so desire.

Challenge 2: Graphing

Create a Chart Component or XY Plot that graphs this path.

Challenge 3: Advanced Inputs

Incorporate advanced input controls to allow the user to change quantities such as the number of points or generate new points / path.

Challenge 4: 3D

Can you write a program that performs the same calculation, but for points in 3D instead of 2D?

Simply specifying the points is not enough! A complete specification must also specify the available edges.

Because if every connection is to be possible, then the shortest path to every point is trivially always the direct connection, if, as stated, the weight of an edge is to be the Euclidean distance.

So what is the complete specification of the challenge? We need a list of edges along with the list of points and the weight information!

By the way, I don't see how the expansion to 3D is supposed to mean a change (apart from the graphic representation with the very poor resources that Prime provides here).

It's also not entirely clear to me what the phrase "Create a Chart Component or XY Plot that graphs this path" in Challenge 2 means.

What does "this path" refers to?

Or does it mean that a destination point should be selected first and the shortest path to it should be displayed?

But as I said, the task first needs to specify how the available edges should be specified.

One (somewhat unsatisfactory) way would be to first randomly enter some (how many?) NaNs or 'infinities' into an adjacency matrix and then fill the rest of the matrix with the Euclidean distances. Of course, it can easily happen that points are not reachable at all, and in the worst case, that not even a single point is reachable from the starting point ;-). A different specification of the edges would therefore be desirable.

BTW, the name is Dijkstra, not Djikstra . See Edsger W. Dijkstra - Wikipedia

I'm glad to see I'm not the only one who keeps misspelling this name ‌‌

D

DaveMartin

Author

16-Pearl

You can consider the available edges to be from each point to every other point. The weight is the distance from the current point to the other points.

W

Werner_E

25-Diamond I

@DaveMartin wrote:

You can consider the available edges to be from each point to every other point. The weight is the distance from the current point to the other points.

That's what I meant when I wrote that in that case we would not need any algorithm because the shortest path always is the direct connection of start end end point. After all we are in Euclidean space.

I don't believe that's what you had in mind.

There would only be further point on the shortest path if three or more points happen to be collinear.

The question of the shortest route only makes sense if not every point is directly accessible from every other point.

Or did I completely misunderstand the task? I thought the task was to use Dijkstra's algorithm to determine the shortest path from the starting point (5;5) to each of the nine points. That is, for each of the nine points, the list of points visited along this path and the total distance traveled.

W

Werner_E

25-Diamond I

So it seems that you are just looking for something like this?

EDIT: Added the 3D version

Prime 10 sheet attached

4_WE_20250902_September_Challenge.zip

W

Werner_E

25-Diamond I

Second version of my sheet.

Fixed an error concerning the selection of the start point.

It should read "nodes3D" here instead of just "nodes".

I also added a comparison of the path found using the greedy algorithm with the real minimal paths (both open and closed).

The minimal paths were found by brute force, calculating the path length for all paths with a constant starting point and all permutations of the remaining points. This is only feasible for a small number of nodes, so I added a threshold which avoids doing the calculation for a larger naumber of nodes. Set it to a higher value at your own risk 😉

We see, that the greedy algorithm sometimes really finds the minimum, often it doesn't but yields a solution which most of the times can be considered a good approximation, given the simplicity of the algorithm.

Prime 10 sheet attached

1_WE_20250905_September_Challenge.zip

N

NickKemaev

12-Amethyst

Super!!!

A

AlanStevens

19-Tanzanite

Here's my best effort using Prime 11 Express (Express isn't really suited to this - the lack of the programming facility is immediately noticeable!):

Alan

1_Sept2025Challenge_AS.zip

2_Sept2025Challenge_AS.pdf

N

NickKemaev

12-Amethyst

Actually, this has already happened, there are plenty of similar examples on the Internet, and there are some here on the forum too.

D

DaveMartin

Author

16-Pearl

Nick,

If you're referring to the challenge itself, my intention isn't to create something that's never been done before or some problem that has baffled people for decades.

When I come up with a challenge, I try to choose something that someone can reasonably do in a couple hours. I don't want people spending ridiculous amounts of time on something they're not getting paid for. I'm glad if there's a previous example they can build on in case they get stuck. (And since it's a community challenge, it's great when someone makes a new worksheet based on one that's already been posted.)

If you check out the blog posts I write following the challenge, I'm more interested in someone's execution than getting the answer. How did they document the worksheet for other people to follow? How did they illustrate the results with plots or charts? How did they use input controls to turn the worksheet into a teaching tool or an engineering resource?

Maybe you can take ones from the PTC Community posts and use it in your submission. (You can even create a hyperlink in the worksheet to the earlier PTC Community post.)

My 2 cents.

Dave

U

uni

13-Aquamarine

Made in 1.5 hours using AI.

tsp_solve Function Overview

I've created (Gemini) a powerful new function, tsp_solve, that integrates a Genetic Algorithm directly into Mathcad to find a near-optimal solution for the Traveling Salesperson Problem (TSP) in 3D Euclidean space.

This function returns the entire optimized route as a matrix, allowing you to visualize the path, calculate open or closed loop distances, and perform further analysis right inside your worksheet.

Function Signature:
tsp_solve(coords, startIndex, gaParams, generations, timeLimit)

Parameters:

coords: An N x 3 matrix where each row represents the (X, Y, Z) coordinates of a city or point.
startIndex: The 0-based index of the city (row in the coords matrix) that should be the starting point of the returned route.
gaParams: A 3x1 vector containing the core parameters for the genetic algorithm:
- gaParams[0,0]: Population Size (e.g., 50) - The number of routes in each generation.
- gaParams[1,0]: Mutation Rate (e.g., 0.02) - The probability (0 to 1) that a city in a route will be swapped.
- gaParams[2,0]: Elitism Count (e.g., 5) - The number of best routes to carry over to the next generation unchanged.
generations: The maximum number of generations the algorithm will run before stopping (e.g., 1000).
timeLimit: A time limit in seconds that also serves as a termination condition (e.g., 10).

The algorithm will stop when either the generations count or the timeLimit is reached. It is also fully responsive and can be interrupted at any time by pressing the Esc key.

Return Value:

The function returns an N x 3 matrix with the same dimensions as the input coords matrix, but with the rows reordered to reflect the optimal path found by the algorithm. The first row of the output matrix will always correspond to the city specified by startIndex.

Links:
1. https://community.ptc.com/t5/Mathcad/Net-User-EFI-interface/td-p/396750

2. https://www.nuget.org/packages/NetEFI.Framework/

The Mathcad Community Challenge September 2025.mcdx document is inside the archive.

Enjoy

1_TspSolver.zip

D

DaveMartin

Author

16-Pearl

Can you post the Mathcad file without the zip file? My computer keeps throwing an error when trying to extract it (the Mathcad worksheet specifically).

David Newman, are you able to extract the zip file?

I apologize to everyone to getting to this late. I moved to Spain at the end of September and promptly caught a cold. I am working to complete the blog post as quickly as possible. Thanks!

D

DJNewman

18-Opal

I'm not able to extract it.

W

Werner_E

25-Diamond I

I found myself unable to resist, and ultimately, I implemented Dijkstra, despite the fact that, excluding its role in inspiring Dave to create the task, Dijkstra is not directly involved in the actual challenge.

The sheet is not heavily documented as there sure are better sources explaining and demonstrating the algorithm easily found on the net.

It's just a quick attempt, which is why it's implemented in MC15. But I guess it should be no problem to convert it to Prime (apart from the usual hassle of having to reformat most parts and maybe also re-label some variables.

I also decided not to include fancy sliders or other components.
Variables for the number of nodes, the number of edges to be removed, and the indices of the start and end nodes must therefore be entered manually. There is also no error checking (e.g., for invalid indices).
Only a button to recalculate the sheet and thus generate new random nodes has been implemented.

Have fun playing around.

3_WE_20250909_Dijkstra.zip

D

DJNewman

18-Opal

I won't be working tomorrow or Wednesday, so I'll BUMP the challenge now.

Closes in a week! Get your submissions and other perspectives in before it's over.

A

AlanStevens

19-Tanzanite

I've produced a 3D version of the original problem in Express. (my first attempt at including a 3D graph was a failure!). More effort required!

Alan

2_Sept2025Challenge_AS_3Da.zip

A

AlanStevens

19-Tanzanite

Now managed to produce a simplistic 3D graph

.

1_Sept2025Challenge_AS_3D.zip

A

AlanStevens

19-Tanzanite

I've been strangely fixated on constructing a 3D graph in Prime 11 Express! Here's my 3D worksheet with an improved 3D graph construction (improved compared with my previous post that is).

Alan

1_Sept2025Challenge_AS_3Db.zip

P

ppal_255687

18-Opal

https://www.wired.com/story/new-method-is-the-fastest-way-to-find-the-best-routes/

W

Werner_E

25-Diamond I

@ppal_255687 wrote:

https://www.wired.com/story/new-method-is-the-fastest-way-to-find-the-best-routes/

Interesting paper about an algorithm which claims to beat Dijkstra - unfortunately the algorithm isn't laid out in detail.

But...

1) Where is your Mathcad or Prime sheet demonstrating the algorithm? 😈

2) While the title here misleading says "Dijkstra", the actual challenge has nothing to do with the Dijkstra algorithm at all. This challenge is about the Travelling Salesman problem which can't be solve using Dijkstra. Dijkstra solves a completely different problem though both deal with "paths of minimal length/costs".
In the Travelling Salesman (the problem this September challenge is all about) a round trip is looked for (if we also should return to the starting point is not specified clearly) and its assumed that every two points are connected.

Dijkstra on the other hand is used to solve a problem similar to what a route planner does - finding the shortest route between two given points and not every point is reachable by every other (otherwise the direct connection would always be the optimal solution).