   Trouble with Dijkstra's algorithm
  Hi,I'm working on a project at the moment in which I am creating a path finding system for a visualisation in a 3D environment. The path finding system will be comprised of a series of nodes at various positions. For the path between each node there will be a physical object representing the path. The idea is then to feed a function a source and destination node name which will then use dijkstra's algorithm to find the shortest path to the destination. That found, a list of path object names will be returned and passed to a function which will make the path objects visible.So i pass in the following: A (source) and E (dest) and get out:A_CC_DD_EI have found a &#106avascript version of a function for the algorithm and it works, but I am having trouble modifying it to suit my needs.Code: http://rafb.net/p/ir13jD10.htmlMy first problem is deciphering what is going on with the variables because they are mostly meaningless letters (at least to me anyway).The second problem is how to output the information above (A_C etc), I've found the bit I need to modify but I'm having trouble understanding it, could someone explain what's going on in this part of the code please://done, now printi=d;if (P < inf) {var thePath = names;var v = i;while (v>0){v = pred[v];if (v>=0) thePath = names[v] + '->' + thePath;}message("Distance:" + P+' ('+thePath+')'+nl);} else {message("no path");}}Thanks alot,eb_dev   
  I can't answer your first problem because I'm not that familiar with the algorithm, but I can answer your second one.A path is basically a list of lines, where each line is represented by a pair of positions: the start and end point of the line. Assuming you use c++, you can write it the following way:std::vector<std::pair<vector3>> path;However since all neighbouring line share a common position, you can reduce the path to a list of positions:std::vector<vector3> path;If you identify your nodes by name, your vector would look like this:std::vector<std::string> path;Outputting however is a very general term, so I can't really answer with specifics because you didn't tell how to visualize them (you could want a list of strings (ie. their names), or a list of lines drawn to the screen).I hope this explaination helps you. If anything's incorrect, beat me with a stick please.//done, now printi=d;// Seems like he is checking if the path is a valid solution or notif (P < inf){// Names is an array of all the node names// And the nodes itself are refered by the index ivar thePath = names;var v = i;// Now he goes through all the nodeswhile( v > 0 ){// They seem to be organized in some sort of linked list// He traverses the path backwards, where pred is an array// that contains the indexes of the nodesv = pred[v];// An index is only valid when it's bigger than or equal to zeroif (v>=0)// Now he builds a string that should look like this: A -> B -> CthePath = names[v] + '->' + thePath;}// When there's a path, he outputs itmessage("Distance:" + P+' ('+thePath+')'+nl);} else {// When there's no solution, he writes thatmessage("no path");};  Hi SiS-Shadowman thanks for your speedy reply.Yes I just need to output as the lines as strings, like:A_CC_DD_EThe strings above will then be sent to a function which displays the corresponding object in the 3D world. It's getting my head around how to change A->C->D->E into the format i need that's the trouble, i understand the while loop is looping through the nodes (which presume are valid nodes in the path?) should i store the previous node in a separate variable and and form my line string that way? The code the person has used has really confused me to be honest, I've never used a while loop in the way it's been used in this example and so I've found it hard to visualise a solution to my problem.I've not come across a linked list before either, i've just had a read on wikipedia but couldn't see how it applied to this example, could you explain further please?Thanks again,eb_dev;  Well, a quick solution would be to collect all the path nodes into a vector(using Shadowman's definition): path.push_back(names[v])The path is now stored reversely, so in order to print the individual steps, you do something like:for(int i = path.size()-1; i > 0; i--){  cout << path.at(i) << "_" << path.at(i-1) << endl;};  That's kind of an ugly hack; a cleaner way to do it would be to use std::reverse from the <algorithm> header, or just use a std::list and push_front instead of push_back to preserve order while you build up the list.   ;  Or, you could just loop from back to front and not even bother to reverse them :P   ;  I suggest you switch to A* over Dijkstra's Algorithm.They're very similar, but A* uses a heuristic function to help to lighten the computation time required by the CPU.http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm has a good discussion of Dijkstra's Algorithm... but really it's just a glorified sort algorithm.As far as the code is concerned...   for(i=0; i<V; i++){P = inf;pred=undef;done=false;}P=0;<br></pre><br><br>Initializes the array to 0, inf, inf, inf… 0 is placed at the start point.<br><br><pre><br>//Re-organized so you can tell wtf is going &#111;n.<br>var v;<br>for(v=0; v&lt;V; v++)<br>{<br>  var minDist = inf, closest = -1;<br>  for (i=0; i&lt;V; i++)<br>  {<br>    if(!done<span style="font-weight:bold;">)<br>    {<br> if(P<span style="font-weight:bold;"> &lt;= minDist)<br> {<br>   minDist = P<span style="font-weight:bold;">; <br>   closest = i;<br> }<br>    }<br>  }<br>  done[closest] = true;<br> <br>  for (i=0; i&lt;V; i++)<br>  {<br>    if (!done<span style="font-weight:bold;">)<br>    {<br> var w = weight(closest, i);<br> if (P[closest]+w &lt; P<span style="font-weight:bold;">)<br> {<br>   P<span style="font-weight:bold;"> = P[closest] + w;<br>   pred<span style="font-weight:bold;"> = closest;<br> }<br>    }<br>  }<br>}<br></pre><br><br>Loops through the list, finding the closest node (first loop will always be the start node). Adds that node to the done list.<br><br>Loops through the remaining nodes, and modifies their distance value, so that when it loops starts the main loop over, it'll have new data to work from.<br><br>Edit:<br>P<span style="font-weight:bold;"> = inf; //Total distance from start node<br>pred<span style="font-weight:bold;">=undef; //Parent node<br>done<span style="font-weight:bold;">=false; //Whether the node has been added to the path or not;  Another way to simplify output without iterating over the result multiple times (and without substantially reorganizing the code) would be to use a doubly linked list.Just add an array "next[V]" and add next[closest]=i after the line pred = closest;Then iterate over the "next" array starting at next[start] and print start + "_" + next[start].However, like Sharsnik said, there might be more efficient algorithms, even more so since the implementation you have here doesn't seem very efficient (complexity is O(n2) -> iterates over all nodes and inside the loop he iterates over all nodes again).;  Binary heaps were made for this problem ;p   ;  Hi Guys,Thanks for all your replies, they're much appreciated.Sharsnik, thanks for the explanation it's making alot more sense now. I'll have a look at the A* algorithm.I've arrived at a solution to my problem, it's probably not the cleanest but it works. I'm working in &#106avascript btw.i=d;if (P < inf) {var thePath = names;var v = i;var prev = null;while (v>0){v = pred[v];if (v>=0) {if(prev != undefined) {thePath = names[v] +"_"+names[prev]+"<br />"+thePath;}else {thePath = names[v] +"_"+thePath;}}prev = v;}message("Distance:" +P+"");message(thePath);} else {message("no path");}}I'm going to modify this now to create an array of path names (A_C,C_F,etc) and then send these to a function which will make my path objects visible.Questions (I'm not a C++ coder):What are linked / doubly linked lists useful for?What are binary heaps?Thanks,eb_dev   