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

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