2
$\begingroup$

I just drew this graph completely random:

Graph

I found the shortest path (marked in red) by simply checking everything. But the reason was to use Dijkstra's algorithm. But when I try I get stuck in a loop. Lake a look at my calculations:

Calculations

How to read it is:

  • Top Row: Wich node
  • Section t: Total distance traveled
  • From: Wich node did I come from
  • The 10 over S and every other section can be read like this
    • To come from S to node 1, the complete path takes 10 time units

So, if you try to follow Dijkstra's algorithm you will get something like this: S->D->C->5->4->6->D->S->5->4->6->D->(and so on)

I get stuck in a loop. I understand that when I return to S I can reset the time to 0, witch make at least the first bit correct, S->5->4, but than it get stuck.

How are you supposed to solve a problem like this based on how the algorithm is formed? For me, it is obviously stupid to just go around this route, but for an algorithm it is not.

Thank you in advance!

$\endgroup$
2
$\begingroup$

Firstly, I suggest that you start off with a simple graph (5 nodes would do). I believe you are mixing Dijkstra with A* search algorithm and are trying to perform A* search (even without knowing it).

For Dijkstra:

  1. Assign to each node a distance value. 0 for initial node and infinity for all other nodes (since they are not visited)
  2. Set initial node as current. Mark other nodes as unvisited. Create a set of all unvisited nodes.
  3. For the current node, consider all of its neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.
  4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.

  5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity, then the algorithm has finished.

  6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

If you need more help on this method, let me know!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.