We need David Eppsteins K-Shortest Path Algorithm implemented in PHP.
[login to view URL]
You should make it OOP program, with the vertices and edges as objects. So for instance (pseudocode)
g = new graph;
$v1 = new vertex(array(val => 1, val => 2));
$v2 = new vertex(array(val => 1, val => 2));
$e = new Edge($v1, $v2, weight)
$paths = $g->kShortestPath($v1, $v2, 5)
So then $paths prints the 5 shortests paths. Preferably your class should be unit tested.