function dijkstra($g,$i){
		$n = sizeof($g['s']);

		$v = array_fill(0, $n, INF);
		$v[$i] = 0;

		$marked = array_fill(0, $n, false);

		$p = array();
		$p[$i] = $i;

		$vmin = 0;
		while($vmin < PHP_INT_MAX){
			$vmin = PHP_INT_MAX;
			for($y=0;$y<$n;$y++){
				if(!$marked[$y] && $v[$y] < $vmin){
					$x = $y;
					$vmin = $v[$y];
				}
			}
			if($vmin<PHP_INT_MAX){
				$marked[$x] = true;
				foreach($g['a'][$x] as $y){
					$g['p'][$x.'.'.$y] = isset($g['p'][$x.'.'.$y]) ? $g['p'][$x.'.'.$y]:1;
					if(!$marked[$y] && $v[$x]+$g['p'][$x.'.'.$y] < $v[$y]){
						$v[$y] = $v[$x]+$g['p'][$x.'.'.$y];
						$p[$y] = $x;
					}
				}
			}
		}
		return $p;
	}