The Student Room Group
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>

Computing Coursework

1.

For my computing coursework I am trying to make a program that calculates the shortest distance between some set points, heres the scenario
- For a person to walk a planned route
- There are 14 "check points" available , but the user only has to visit 10 (the start and end point count as one of the 10, so it's only 8 inbetween)
- The user can select a start and end point
I want the program to calculate the shortest route, once the start and end points have been input, and then output the order.
I have been told that possibly dijkstra's algorithm or Prims algorithm would be suitable, but I am unsure, which algorithm (s) should I use and how should I go about it?

Sorry you've not had any responses about this. :frown: Are you sure you’ve posted in the right place? Posting in the specific Study Help forum should help get responses. :redface:

I'm going to quote in Puddles the Monkey now so she can move your thread to the right place if it's needed. :h: :yy:

Spoiler

Original post by Hazzer98

1.

For my computing coursework I am trying to make a program that calculates the shortest distance between some set points, heres the scenario
- For a person to walk a planned route
- There are 14 "check points" available , but the user only has to visit 10 (the start and end point count as one of the 10, so it's only 8 inbetween)
- The user can select a start and end point
I want the program to calculate the shortest route, once the start and end points have been input, and then output the order.
I have been told that possibly dijkstra's algorithm or Prims algorithm would be suitable, but I am unsure, which algorithm (s) should I use and how should I go about it?



Prims algorithm finds the minimum spanning tree so would use all 14 nodes, not what you want. Djikstras algorithm finds the shortest path between two nodes so you could use that if you added an extra condition so that 10 nodes are used.

Make sure you understand programming graphs and how Djikatras algorithm works, then it shouldnt be too hard.
Original post by Hazzer98

1.

For my computing coursework I am trying to make a program that calculates the shortest distance between some set points, heres the scenario
- For a person to walk a planned route
- There are 14 "check points" available , but the user only has to visit 10 (the start and end point count as one of the 10, so it's only 8 inbetween)
- The user can select a start and end point
I want the program to calculate the shortest route, once the start and end points have been input, and then output the order.
I have been told that possibly dijkstra's algorithm or Prims algorithm would be suitable, but I am unsure, which algorithm (s) should I use and how should I go about it?


What language and program/API are you writing this in? People will suggest a lot of fancy algorithms but personally, for ease of use, I'd just have an array of distances, have a for loop to calculate all of the distances, then return the shortest one by a comparison each time the loop increments. Whether you're doing this in 2D or 3D, you can use simple vector maths to calculate the actual distances.
Reply 4
Avatar for Async
Async
19
Original post by General Josh
What language and program/API are you writing this in? People will suggest a lot of fancy algorithms but personally, for ease of use


This is the complete opposite of what they want you to do in the Computing Coursework. They want you to do things the hardest way possible in order to achieve more marks. Plus bringing in concepts learnt from decision maths helps boost your grade.
Original post by Async
This is the complete opposite of what they want you to do in the Computing Coursework. They want you to do things the hardest way possible in order to achieve more marks. Plus bringing in concepts learnt from decision maths helps boost your grade.


Ah, I hadn't considered that, I was thinking it's just be nice to do something like (vec3 diff = b - a; float distance = sqrtf(dot(diff, diff)):wink:, presuming you're in c++. Having said that, if you haven't used vector maths before it could be difficult, but if you're looking for a nice complicated way of doing it, I'd definitely go with Dijkstra's Algorithm over Prim's.

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you