迪杰斯特拉算法

CTCSU · CTCSU · commit bc9c752251ff · 2018-01-27T11:43:08.000+08:00
diff --git a/src/main/java/BreadthFirstSearch.java b/src/main/java/BreadthFirstSearch.java
@@ -1,5 +1,11 @@
 import java.util.*;
 
+/**
+ * 广度优先搜索;
+ * 图的搜索算法,对每个节点:搜索其子节点(相连节点),如果该节点被搜索过,那么就跳过,否则加入到搜索节点队列;当前节点完成后,从队列中选择
+ * 第一个节点继续搜索.直到队列中不再有节点.
+ *
+ */
 @SuppressWarnings("unused")
 public class BreadthFirstSearch implements AlgorithmInGraph{
 
@@ -10,7 +16,6 @@ public void showAlgorithm() {
         List<Integer> orders = search(graph);
         System.out.println("广度优先搜索的节点依次为(从0节点开始搜索):");
         System.out.println(Arrays.toString(orders.toArray()));
-
     }
 
     public List<Integer> search(int [][] graph){
diff --git a/src/main/java/Dijkstra.java b/src/main/java/Dijkstra.java
@@ -0,0 +1,103 @@
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+public class Dijkstra implements AlgorithmInGraph {
+
+    public void showAlgorithm() {
+
+        int [][] graph = new int [5][5];
+        //不可达
+        for(int i = 0;i<5;i++){
+            for(int j = 0;j<5;j++){
+                graph[i][j] = i == j? 0:-1;
+            }
+        }
+
+        graph[0][1] = 9;
+        graph[0][2] = 2;
+        graph[0][3] = 3;
+        graph[1][3] = 4;
+        graph[2][4] = 4;
+        graph[3][2] = 2;
+        graph[3][4] = 1;
+
+        GraphSearchUtil.printGraph(graph);
+        List<Integer> nodes = doDijkstra(graph,0,4);
+        System.out.println(Arrays.toString(nodes.toArray()));
+    }
+
+    private List<Integer> doDijkstra(int [][] graph,int start,int end) {
+
+        int length = graph.length;
+        int[] minimumValue = new int[length];
+
+        //表示当前不可达
+        for (int i = 0; i < length; i++) {
+            minimumValue[i] = Integer.MAX_VALUE;
+        }
+
+
+        int[] minmimumNode = new int[length];
+        for(int i=0;i<length;i++){
+            minmimumNode[i] = -1;
+        }
+
+        List<Integer> examinedNode = new ArrayList<Integer>();
+
+        //存放当前最小值的节点
+        minimumValue[start] = 0;
+        minmimumNode[start] = start;
+
+
+
+        int currentNode = start;
+
+        int index = 0;
+        boolean continueSeach = true;
+        while (continueSeach) {
+            continueSeach = false;
+            for (int i = 0; i < length; i++) {
+                if (graph[currentNode][i] < 0) {
+                    continue;
+                }
+                if (graph[currentNode][i] + minimumValue[currentNode] < minimumValue[i]) {
+                    minimumValue[i] = graph[currentNode][i] + minimumValue[currentNode];
+                    minmimumNode[i] = currentNode;
+                }
+            }
+            //已经检查过的节点
+            examinedNode.add(currentNode);
+
+            //从当前节点中选择一个最小的节点值
+            int minmum = Integer.MAX_VALUE;
+            for (int i = 0; i < length; i++) {
+                if (!examinedNode.contains(i) && minimumValue[i] < minmum) {
+                    currentNode = i;
+                    minmum = minimumValue[i];
+                    continueSeach = true;
+                }
+            }
+        }
+
+        //不可达
+        if(minmimumNode[end] == -1){
+            return null;
+        }else{
+
+            System.out.println(Arrays.toString(minmimumNode));
+            List<Integer> reversResult = new ArrayList<Integer>();
+            int node = end;
+            while(node != start){
+                reversResult.add(minmimumNode[node]);
+                node = minmimumNode[node];
+            }
+
+            List<Integer> result = new ArrayList<Integer>();
+            for(int i = reversResult.size() - 1;i>=0;i--){
+                result.add(reversResult.get(i));
+            }
+            return  result;
+        }
+    }
+}
diff --git a/src/test/java/AlgorithmInGraphTest.java b/src/test/java/AlgorithmInGraphTest.java
@@ -6,7 +6,7 @@ public class AlgorithmInGraphTest {
 
     @Test
     public void showAlgorithm() throws ClassNotFoundException, IllegalAccessException, InstantiationException {
-        AlgorithmInGraph algorithm = (AlgorithmInGraph) Class.forName("BreadthFirstSearch").newInstance();
+        AlgorithmInGraph algorithm = (AlgorithmInGraph) Class.forName("Dijkstra").newInstance();
         algorithm.showAlgorithm();
 
 
