0

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 ?

Brad Werth
  • 17,411
  • 10
  • 63
  • 88
David Bélanger
  • 7,400
  • 4
  • 37
  • 55
  • 1
    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 Sep 20 '12 at 21:43
  • 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 Sep 20 '12 at 21:44
  • 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 Sep 20 '12 at 21:47
  • 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 Sep 20 '12 at 21:48
  • 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 Sep 20 '12 at 21:50
  • Think of the nodes as cities. The distance between two directly connected cities is constant. The first value is one gps coordinate, the second one aswell, and the third is the distance between them. Is your question how to get the initial distance between two nodes? – kmindi Sep 20 '12 at 21:50
  • http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates will get you the third value (direct air connection not on street). After that you can use dijkstra's algorithm to calculate distance between any two of them over others from your array/list – kmindi Sep 20 '12 at 21:52
  • Yes. I don't know what to write in the third value `array(4142193, 601021, ??)`. If I calculate the distance using the GPS coords, will it work ? – David Bélanger Sep 20 '12 at 21:54

3 Answers3

3

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

kmindi
  • 4,524
  • 4
  • 31
  • 47
  • Nice. However, this algo require 2 points. 2 X and 2 Y. I don't understand how I can use this to find the distance using one point `array(4142193, 601021, ??)` – David Bélanger Sep 20 '12 at 22:01
  • Dijkstra operates on arbitrary graphs where you can define the weight or distance like you want. IF you have latitude and longitude information (e.g. from OSM) for every node you can calculate the real distance. I think, one id like 4142193 maps directly to one node. So e.g. you are importing the data from OSM you start from id=0 and then fill up another latitude array (as well as the longitude array) with latitudes. then you can get the latitudes via latitude[0] for node 0 etc and get the required lat,lon for both ids to calculate the real distance – Karussell Sep 21 '12 at 12:11
1

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.

fgb
  • 18,439
  • 2
  • 38
  • 52
0

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.

Patrick Raphael
  • 43
  • 4
  • I understand better now, thanks. So now I know that there's 2 points (not x and y) and the distance between them. It's soooo much clear for me now. One last question, do I need to calculate the distance between all points ? Let's say I have 3000 nodes arround in a city. Do I need to calculate the distance between the farest one in the north and the south per example ? – David Bélanger Sep 21 '12 at 02:53
  • When you run Djikstra's algorithm, you end up calculating the shortest path between a single node, and all nodes on the graph. But that doesn't given you the shortest path between ALL nodes. You could rerun Djikstra's algorithm for every node, but there are much more effiicent ways to do this (the Floyd-Warshall algorithm) – Patrick Raphael Sep 21 '12 at 18:52