StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think you might be a bit confused as to the problem. Djistrka's algorithm operates on a graph, either directed or undirected. I'm not sure if the graph given is supposed to be directed or not. (If its undirected, then array(n1, n2, d) also implies array(n2, n1, d)</p> <p>A graph does not have to have physical x,y coordinates. You can simply have a list of vertices, or nodes, and the distance between them.</p> <p>The data structure given may not be the best way to visualize the problem. A better way might be the following:</p> <pre><code>$points = array( array(0, array(1, 4). arrau(2. 1)), array(1, array(2, 5). array(3. 5)), array(2, array(3,5), array(10, 30), array(11, 30), array(3, array(4,5)), array(4, array(5,5)), array(5, array(19,20)), array(10, array(11,20)), array(12, array(13,20))) </code></pre> <p>In pseudo-code, this represents</p> <pre><code>Node 0 -> Node 1 (distance 4), Node 2 (distance 1) Node 1 -> Node 2 (distance 1), Node 3 (distance 5) etc. </code></pre> <p>Assuming this is directed, which simplifies the problem a bit, this array now represents the connectivity for all nodes. For instance, node 0 is connected to two nodes, node 1 and node 2. Node 1 is connected to 3 nodes, node 2 and node 3. Node 3 is connected to just one node, node 4. </p> <p>We might be intersted in the following problem: starting at node 0, how would we get to node 4? One route would be Node 0 to Node 1 (distance 4) to Node 3 (distance 5) to Node 4 (distance 5). The total distance travelled would be 4 + 5 + 5 = 14. </p> <p>Now we ask the question: is that the shortest route? Since the graph is so small and not very well connected, in this case you can see it is. The only way to get to Node 4 is coming from node 3, and the only way to get to node 3 is by coming from either node 2 or node 1. To get to Node 2, we can come from Node 0 or node 1. But going through node 1 is just going to make the trip longer, so its obvious the solution is Node 0 -> Node 2 -> Node 3 -> Node 4.</p> <p>Hope that clarification helps.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload