Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Help with impletementing dijkstra's Algorithm

imhiyaimhiya Member Posts: 3
I have two files; one with places then the distance between them.

Example:
Moffat Carlisle 65
Doncaster Hull 76
Northampton Birmingham 90
Leicester Lincoln 82
Sheffield Birmingham 122


I was wanting to use dijkstra's method, but i seem to have a problem because looking pseudo codes to understand it they all ask for a node, then all the connecting nodes. The problem is that the file is unordered so it will keep changing nodes. I thought i could search if it's already in the array/vector. If not then add it, but the problem with this is i don't know how many connecting nodes there is, so i would have to include a expanding varible.

The second file, contains a source city and dest city, which i have to work out the shortest path.

hope you can help!

Comments

  • nebgastnebgast Member Posts: 54
    Don't have much time to respond right now, but I figured I'd at least point you in a direction on one of the things that seems to be majorly stumping you.

    For something like Dijkstra's algorithm, an array/vector isn't the data type you really want to use to store the information. Cause like you said as nodes are added you would need to resize which can be an expensive operation. The data type I would recommend using would be a list. This way you can add nodes infinitely. Only thing being of how the list is made and the lowest search time you can reach to find whether or not a node already exists on any given list.

    Hope that helps somewhat. When I get more time I'll come back an add some more if no one else has chimed in.
  • imhiyaimhiya Member Posts: 3
    Thank you for the reply, How would i setup multiple list's connected to one node though?
Sign In or Register to comment.