1 | <?php |
||
22 | class DijkstraTest extends \PHPUnit_Framework_TestCase { |
||
23 | /** |
||
24 | * An undirected graph, with non-negative edge values. |
||
25 | * No two shortest paths exist with the same length. |
||
26 | * |
||
27 | * D---9---E |
||
28 | * / \ \ |
||
29 | * 14 2 6 |
||
30 | * / \ \ |
||
31 | * A---9---B--11--C |
||
32 | * \ / / |
||
33 | * 7 10 / |
||
34 | * \ / / |
||
35 | * F-----15 |
||
36 | * |
||
37 | * |
||
38 | * @var integer[][] Test graph |
||
39 | */ |
||
40 | private $graph1 = array( |
||
41 | 'A' => array('B' => 9, 'D' => 14, 'F' => 7), |
||
42 | 'B' => array('A' => 9, 'C' => 11, 'D' => 2, 'F' => 10), |
||
43 | 'C' => array('B' => 11, 'E' => 6, 'F' => 15), |
||
44 | 'D' => array('A' => 14, 'B' => 2, 'E' => 9), |
||
45 | 'E' => array('C' => 6, 'D' => 9), |
||
46 | 'F' => array('A' => 7, 'B' => 10, 'C' => 15), |
||
47 | ); |
||
48 | |||
49 | /** |
||
50 | * Test that there are no paths to/from 'G'. |
||
51 | * |
||
52 | * @return string[] |
||
53 | */ |
||
54 | public function testNoPath() { |
||
60 | |||
61 | /** |
||
62 | * Test that there is a null paths to/from the same node. |
||
63 | * |
||
64 | * @return string[] |
||
65 | */ |
||
66 | public function testNullPath() { |
||
71 | |||
72 | /** |
||
73 | * Test there is a unique shortest path from 'A' to every other node. |
||
74 | * |
||
75 | * @return string[] |
||
76 | */ |
||
77 | public function testUniqueShortestPath() { |
||
95 | |||
96 | /** |
||
97 | * Test the multiple shortest paths between 'E' and 'F'. |
||
98 | * |
||
99 | * @return string[] |
||
100 | */ |
||
101 | public function testMultipleShortestPaths() { |
||
107 | |||
108 | /** |
||
109 | * Test the exclusion list, for next-shortest paths. |
||
110 | * |
||
111 | * @return string[] |
||
112 | */ |
||
113 | public function testExclusionList() { |
||
119 | } |
||
120 |