Dijkstra algorithm - how to calculate distance?

0
votes

I got the PHP class from the website : http://www.giswiki.org/wiki/Algorithmus_von_Dijkstra

In the code I see :

// $points is an array in the following format: (router1,router2,distance-between-them)
$points = array(
    array(0,1,4),
    array(0,2,I),
    array(1,2,5),
    array(1,3,5),
    array(2,3,5),
    array(3,4,5),
    array(4,5,5),
    array(4,5,5),
    array(2,10,30),
    array(2,11,40),
    array(5,19,20),
    array(10,11,20),
    array(12,13,20),
);

What is the math to get the "distance-between-them" ? I cannot figure out the math behind that.

I have WSG84 coords (GPS... example: 56.292157,-88.022461). I did the math to get the same coordinates in UTM (UTM give number X and Y, I got 4142193, 601021). I got my first and second value to populate my array. I don't know how to get the distance for the third value.

Any clues ?

3
phpalgorithmdijkstra
Are you interested in how the algorithm calculates the distances from one node to every other node with a greedy strategy or how to get the results like in the example you linked? – kmindi
Look at the array. Let's say I take this entry array(2,10,30) - how he get 30 ? Because what I wanna do is to create a routing script in PHP. – David Bélanger
That array represents the pre-defined distances between two nodes. That distance does not change. The algorithm will calculate distances between one specified node two every other reachable node (via a route over other nodes) – kmindi
Ok so what I do with the third value ? I'll use UTM value for value 1 and 2 but what do I input in the third one ? – David Bélanger
If I could use WSG84 to calculate a path that would be answome, but I haven't found. I saw this class that use X and Y value so I tought of the UTM system but I can't figure out the third value. – David Bélanger

3 Answers

3
votes

The third value should be calculated using the Great-circle_distance algorithm. Then you can use dijkstra's algorithm.

1
votes

The first two numbers aren't coordinates - they're indexes. So you'll need to give each of your points a unique index that can be used to refer back to the point.

array(0, 1, 4) means that the distance between point 0 and point 1 is 4. The units for the distance can be whatever you want.

0
votes

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)

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.

The data structure given may not be the best way to visualize the problem. A better way might be the following:

$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)))

In pseudo-code, this represents

Node 0 -> Node 1 (distance 4), Node 2 (distance 1)
Node 1 -> Node 2 (distance 1), Node 3 (distance 5)
etc.

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.

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.

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.

Hope that clarification helps.