monkeycoderw
diff --git a/‎.test.php.swp
0 Bytes b/‎.test.php.swp
0 Bytes
diff --git a/‎Graphic/.GraALG.php.swp
12 KB b/‎Graphic/.GraALG.php.swp
12 KB
diff --git a/‎Graphic/GraALG.php
Lines changed: 53 additions & 24 deletions b/‎Graphic/GraALG.php
Lines changed: 53 additions & 24 deletions
diff --git a/‎Graphic/Vertex.php
Lines changed: 2 additions & 0 deletions b/‎Graphic/Vertex.php
Lines changed: 2 additions & 0 deletions
diff --git a/‎test.php
Lines changed: 2 additions & 1 deletion b/‎test.php
Lines changed: 2 additions & 1 deletion
@@ -11,20 +11,22 @@ class GraALG {
     public $edges;
     //邻接表
     public $graphic;
-   
-    //dijkstr用来记录最短路径和前置节点
-    public $dijkstra;
     //邻接矩阵表示
     public $adjMatrix;
-   
-    public function __construct($verex, $edges, $graphic) {
+    //Floyd最短路径算法
+    public $depth;
+    public $path;
+
+    public function __construct($verex, $edges, $graphic)
+    {
         $this->verex = $verex;
         $this->edges = $edges;
         $this->graphic = $graphic;
     }
 
     //深度优先
-    public function DFS($tail) {
+    public function DFS($tail)
+    {
         //do sth, not only echo
         echo $tail;
         foreach ($this->graphic[$tail] as $heads) {
@@ -37,7 +39,8 @@ public function DFS($tail) {
     }
 
     //深度优先,depth_first_search
-    public function DFSTraverse() {
+    public function DFSTraverse()
+    {
         foreach ($this->verex as $ver) {
             if ($ver->visited == 0) {
                 $this->DFS($ver->name);
@@ -47,7 +50,8 @@ public function DFSTraverse() {
 
     //广度优先,breadth_first_searth
     //array_pop取出最后一个值,array_shift取出第一个值,array_push
-    public function BFSTraverse() {
+    public function BFSTraverse()
+    {
         $queue = array();
         $queue [] = $this->verex['A']->name;
         $this->verex[$vex]->visited = 1;
@@ -69,7 +73,8 @@ public function BFSTraverse() {
     }
 
     //邻接表转换成邻接矩阵
-    public function toAdjMatrix() {
+    public function toAdjMatrix()
+    {
         $this->adjMatrix = array();
         foreach ($this->verex as $vex_i) {
             $arr = array();
@@ -85,21 +90,45 @@ public function toAdjMatrix() {
         }        
     }
 
-    //最短路径的问题,$dijkstra,邻接矩阵表示$adjMatrix;
-    public function shortestPathDijkstrai() {
-        $pre      = 0;
-        $shortest = 1;
-        $this->dijkstra = array(); 
-        //第一个数值表示本节点的前置节点为0，
-        //第二个数值表示本节点到源点的最短距离
-        $row = array(0, 0);
-        $this->dijkstra [0] = $row;
-        $this->verex[0]->visited = 1;
-
-        foreach ($this->verex as $vex) {
-            if ($vex->visited == 0) {
-                
+    //最短路径问题,Dijkstra算法,邻接矩阵表示$adjMatrix;
+    public function shortestPathDijkstra($source)
+    {
+        foreach($this->verex as $vex) {
+            $vex->visited  = 0;
+            $vex->pre      = 0;
+            $vex->shortest = $this->adjMatrix[$source][$vex->name];
+        }
+        $this->verex[$source]->visited = 1;
+        $this->verex[$source]->shortest = 0;
+        foreach ($this->verex as $verer) {
+            $min = self::INFINITY;
+            $key = 0;
+            foreach ($this->verex as $vex) {
+                if ($vex->visited == 0 && $vex->shortest < $min) {
+                    $min = $vex->shortest;
+                    $key = $vex->name;                    
+                    echo $min.'--'.$key, PHP_EOL;
+                }
             }
-        }       
+            echo $key,PHP_EOL;
+            $this->verex[$key]->visited = 1;
+            foreach ($this->verex as $vex) {
+                if ($vex->visited == 0 &&
+                        $vex->shortest > $min + $this->adjMatrix[$key][$vex->name]) {
+                    $vex->pre = $key;
+                    $vex->shortest = $min + $this->adjMatrix[$key][$vex->name];
+                }
+            }
+        }
+    }
+
+    public function shortestFloyd()
+    {
+        //$this->depth;
+        //$this->path;        
+        $length = count($this->verex);
+        for ($i=0; $i < $length; $i++) {
+            
+        }
     }
 }
@@ -6,6 +6,8 @@ class Vertex {
     public $name;
     public $data;
     public $visited;
+    public $pre;
+    public $shortest;
 
     public function __construct($name, $data = 0, $visited = 0) {
         $this->name = $name;
 
@@ -44,4 +44,5 @@
 #$graphic->DFSTraverse();
 #$graphic->BFSTraverse();
 $graphic->toAdjMatrix();
-print_r($graphic->adjMatrix);
+$graphic->shortestPathDijkstra(0);
+print_r($graphic->verex);