即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

迪杰斯特拉(Dijkstra)算法求解单源最短路径(java)

编程语言 Recall_Tomorrow 39℃ 0评论
package ccnu.offer.graph;

import java.util.ArrayList;
import java.util.Arrays;

public class Demo02 {
    public static void main(String[] args) {
        int vertexNum = 5;
        char[] vertexs = new char[] { 'A', 'B', 'C', 'D', 'E' };
        int[][] matrix = new int[][] { { Integer.MAX_VALUE / 2, 10, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 5 }, 
                                       { Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 1, Integer.MAX_VALUE / 2, 2 }, 
                                       { Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 4, Integer.MAX_VALUE / 2 }, 
                                       { 7, Integer.MAX_VALUE / 2, 6, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2 },
                                       { Integer.MAX_VALUE / 2, 3, 9, 2, Integer.MAX_VALUE /2 } };
       Graph g = new Graph(vertexNum, vertexs, matrix);
       char[] pathSerials = dijkstra(g, 0);
       for(char vertex : pathSerials){
           System.out.print(vertex);
       }
    }   

    // 通过迪杰斯特拉(Dijkstra)算法求以vertex[i]顶点作为源点到其余各顶点的最短路径
    public static char[] dijkstra(Graph g, int i) {
        char[] pathSerials = new char[g.vertexNum];
        char[] path = new char[g.vertexNum];
        Arrays.fill(path, '#'); // #表示木有前驱顶点
        int index = 0;
        pathSerials[index] = g.vertexs[i]; // 源点加入序列中
        g.visited[i] = true; // 源点已在最短路径序列中
        int[] distances = new int[g.vertexNum];
        Arrays.fill(distances, Integer.MAX_VALUE / 2);
        for (int ii = 0; ii < g.vertexNum; ii++) {
            if (!g.visited[ii]) {
                distances[ii] = g.matrix[i][ii];
            }
        }
        int minIndex = i;
        while (minIndex != -1) {
            index++;
            for (int iii = 0; iii < g.vertexNum; iii++) {
                if (!g.visited[iii]) { // 更新仍未加入到最短路径序列中的顶点的从源点到它的值
                    // 这些仍未加入到最短路径序列中的顶点的distances[iii]值为(刚加入的顶点minIndex的distances[minIndex]与minIndex到顶点iii之和)与(顶点minIndex刚加入之前源点到iii的距离值distances[iii])两者之间的较小者
                    distances[iii] = Math.min(distances[iii], distances[minIndex] + g.matrix[minIndex][iii]);
                }
            }
            int preMinIndex = minIndex;
            minIndex = indexOf(g, distances);
            if(minIndex == -1){
                break;
            }
            if(distances[minIndex] == distances[preMinIndex] + g.matrix[preMinIndex][minIndex]){
                path[index] = g.vertexs[preMinIndex];
            }else{
                path[index] = path[index - 1];
            }
            if(index == 1){
                path[index] = g.vertexs[preMinIndex];
            }
            pathSerials[index] = g.vertexs[minIndex];
            g.visited[minIndex] = true;
        }
        for(char ch : path){
            System.out.print(ch);
        }
        System.out.println();
        return pathSerials;
    }

    // 找到图中仍未加入到最短路径序列顶点集中到源点距离最小的顶点的索引
    public static int indexOf(Graph g, int[] distances) {
        int min = Integer.MAX_VALUE / 3;
        int minIndex = -1; // 当前数组distances剩余元素最小值(-1表示无剩余元素)--剩余元素就是仍未加入到最短路径序列中的顶点
        for(int i = 0; i < g.vertexNum; i++){
            if(!g.visited[i]){ // 如果i顶点仍未加入到最短路径序列中
                if(distances[i] < min){
                    min = distances[i];
                    minIndex = i;
                }
            }
        }
        return minIndex;
    }

    public static class Graph{
        private int vertexNum;
        private char[] vertexs;
        private int[][] matrix;
        private boolean visited[];

        public Graph(int vertexNum, char[] vertexs, int[][] matrix){
            this.vertexNum = vertexNum;
            this.vertexs = vertexs;
            this.matrix = matrix;
            visited = new boolean[vertexNum];
        }
    }

    public static class Info{
        private int[] distances;
        private char[] pathSerials;
        private ArrayList paths;

        public Info(int[] distances, char[] pathSerials){
            this.distances = distances;
            this.pathSerials = pathSerials;
        }

    }
}

转载请注明:CodingBlog » 迪杰斯特拉(Dijkstra)算法求解单源最短路径(java)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情