daily pastebin goal
6%
SHARE
TWEET

Untitled

a guest Feb 11th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function dijkstra($g,$i){
  2.         $n = sizeof($g['s']);
  3.  
  4.         $v = array_fill(0, $n, INF);
  5.         $v[$i] = 0;
  6.  
  7.         $marked = array_fill(0, $n, false);
  8.  
  9.         $p = array();
  10.         $p[$i] = $i;
  11.  
  12.         $vmin = 0;
  13.         while($vmin < PHP_INT_MAX){
  14.             $vmin = PHP_INT_MAX;
  15.             for($y=0;$y<$n;$y++){
  16.                 if(!$marked[$y] && $v[$y] < $vmin){
  17.                     $x = $y;
  18.                     $vmin = $v[$y];
  19.                 }
  20.             }
  21.             if($vmin<PHP_INT_MAX){
  22.                 $marked[$x] = true;
  23.                 foreach($g['a'][$x] as $y){
  24.                     $g['p'][$x.'.'.$y] = isset($g['p'][$x.'.'.$y]) ? $g['p'][$x.'.'.$y]:1;
  25.                     if(!$marked[$y] && $v[$x]+$g['p'][$x.'.'.$y] < $v[$y]){
  26.                         $v[$y] = $v[$x]+$g['p'][$x.'.'.$y];
  27.                         $p[$y] = $x;
  28.                     }
  29.                 }
  30.             }
  31.         }
  32.         return $p;
  33.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top