-
Notifications
You must be signed in to change notification settings - Fork 4
/
dijkstra.php
69 lines (51 loc) · 1.82 KB
/
dijkstra.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
<?php
require './src/Dijkstra.php';
/**
* Require the data for the algorithm.
* For this I'm going to read from a CSV file with random data.
*/
$filename = 'data.csv';
/**
* The graph structure holds 'origin', 'destination' and 'weight'. That's all we need for this algorithm.
* We need it this way:
* [origin1]
* [destination1] => weight
* [destination2] => weight
* ...
*/
$graph = array();
// Open the data file for reading and construct adjacency list.
// IMPORTANT: elements of the CSV are suposed to be separated by semicolon (;).
if (($h = fopen("{$filename}", "r")) !== FALSE) {
// Each line in the file (except the first one) is converted into an individual array that we call $data
$i = 0;
while (($data = fgetcsv($h, 1000, ";")) !== FALSE) {
if ($i > 0) {
$originID = (int)$data[0];
$destinationID = (int)$data[1];
$graph[$originID][$destinationID] = $data[2];
}
$i++;
}
fclose($h);
}
// Source is the origin node we are going to search from.
$source = 5950;
// Start Dijkstra's algorithm with graph and source, indicating it is a directed graph.
$dijkstra = new Dijkstra($graph, $source, true);
// And now, let's show some results...
echo "Time of calculation: ".$dijkstra->getAlgorithmTime()." seconds.\n\n";
// Show the Distances and Previous arrays.
echo "Distances array: \n";
print_r($dijkstra->getDistances());
echo "\nPrevious array: \n";
print_r($dijkstra->getPrevious());
// And show the shortest distance to a couple of Vertices.
$destination = 9583;
$shortest_path1 = $dijkstra->shortestPathTo($destination);
echo "\nShortest path to 9583: \n";
print_r($shortest_path1);
$destination = 4907;
$shortest_path2 = $dijkstra->shortestPathTo($destination);
echo "\nShortest path to 4907: \n";
print_r($shortest_path2);