# Dijkstra

Jul 25th, 2021 (edited)
384
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. <?php
2.     private \$INT_MAX = 0x7FFFFFFF;
3.     private \$known = [];
4.     private \$distance = [];
5.     private \$path = [];
6.     private \$paths = [];
7.
8.     function ShortestViaNode() {
9.         \$min = \$this->INT_MAX;
10.         \$minIndex = 0;
11.
12.         for (\$v = 0; \$v < \$this->siz; \$v++) {  // if v unknown and the distance to there (from start) <= min, this is the new min way node.
13.             if (\$this->known[\$v] == false && \$this->distance[\$v] <= \$min) {
14.                 \$min = \$this->distance[\$v];
15.                 \$minIndex = \$v;
16.             }
17.         }
18.         return \$minIndex;
19.     }
20.
21.     function Dijkstra(\$graph, \$start) {
22.         \$this->siz = sizeof(\$graph);
23.
24.         for (\$i = 0; \$i < \$this->siz; \$i++) {
25.             \$this->distance[\$i] = \$this->INT_MAX;
26.             \$this->known[\$i] = false;
27.             \$this->path[\$i] = -1;
28.         }
29.         \$this->paths[\$i-1][] = -1;
30.
31.         \$this->distance[\$start] = 0; // startpoint (0) is done. Let's iterate 1..all
32.
33.         for (\$i = 0; \$i < \$this->siz; \$i++) { // this \$i is else then the before one! It just counts...
34.             \$u = \$this->ShortestViaNode(); // u is the node through the shortest node, when \$start->\$i
35.             \$this->known[\$u] = true;       // we set u as known
36.
37.             for (\$v = 0; \$v < \$this->siz; \$v++)
38.             // let's iterate all the nodes. Maybe there is a shortest way than we know until now...
39.             // if v is unknown & there is edge u->v & distance]u] is finite &  distance[u]+ u->v < distance[v] then it is the new distance.
40.             // changed last ... < ...dist... to <=, allowing equation also for ALL paths
41.                 if (!\$this->known[\$v] && \$graph[\$u][\$v] && \$this->distance[\$u] != \$this->INT_MAX && \$this->distance[\$u] + \$graph[\$u][\$v] <= \$this->distance[\$v]) {
42.                     \$this->distance[\$v] = \$this->distance[\$u] + \$graph[\$u][\$v];
43.                     //¤ print \$v.":".\$u.";".\$this->distance[\$v].n;
44.                     \$this->path[\$v] = \$u;
45.                     \$this->paths[\$v][] = \$u;
46.                 }
47.         }
48.     }
RAW Paste Data Copied