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

[DaveMartin]

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.

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!

[Werner_E]

---

@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 ‌‌ 

[DaveMartin]

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.

[Werner_E]

---

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

[DaveMartin]

There is no specified end point. Only a start point.

Let me give an example. Let's say we have points A, B, C, D, E, and F. A is the start point.

We then look at the distances from A to B, C, D, E, and F. Let's say that the distance from A to E is the shortest. That is the path we take. Now we're starting at E. In case I need to say it, once we visit a point, we can't go back to it. Now we look at the distances from E to B, C, D, and F. Let's say the shortest distance is to C. That is our next point. From C, we can now measure the distances from B, D, and F. The shortest path is where we go. Until we visit all the points.

And for this challenge, you don't even have to start at (5, 5) like I specified.

[Werner_E]

So what you have in mind is kind of a round trip but without closing it - we do not have to come back to the starting point. The distance from the last point visited back to the start is not taken in account, correct?

Actually a travelling salesman problem but solved just using (local) greedy algorithm which most of the times won't find the optimal route.

And because the round trip is not closed and because only a simply greedy algorithm should be implemented, changing the starting point usually will result in a different route.

I misunderstood when you wrote "shortest path from the first node (5,5) to all other nodes" because I interpreted it in the sense it has in Dijkstra - which would mean to calculate the shortest route from start to A, and also the shortest from start to B, etc.
So I thought you wanted us to implement the Dijkstra algorithm which would have made no sense if all points are connected

But the challenge actually has nothing to with Dijkstra, correct?

[DJNewman]

---

@Werner_E wrote:

---

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 ‌‌ 

---

I'm glad I'm catching this now before I promote this more...widely.

[Werner_E]

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

EDIT: Added the 3D version

Prime 10 sheet attached

[Werner_E]

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

[NickKemaev]

Super!!!

[AlanStevens]

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

[NickKemaev]

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

[DaveMartin]

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

[Werner_E]

For whatever it may be worth, here is the original post about the Traveling Salesman by Valery

Travelling Salesman Problem

and here a follow up by Alan

Valery's Travelling Salesman Problem

Could not find an implementation of Dijkstra here in the forum, but the challenge isn't dealing with Dijkstra anyway.
Incidentally, Dijkstra is not an algorithm that finds the optimal or near-optimal solution to the Traveling Salesman Problem, which is the subject of this challenge. Dijkstra finds the optimal route from a given start point to any given endpoint or all possible endpoints.

[AlanStevens]

Here's a slightly cleaner set of the iterative calculations in my worksheet.

If only the row select would accept the function fn(L) instead of insisting on an integer, I could create a single line function with L:=0..n-2.

 

Alan

[uni]

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

[Werner_E]

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.