szabozoltan69

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