function[P,d] = fun_Dijkstra(G,start,End)
% 建立权重矩阵
% 判断是否存在权重矩阵，如果不存在，那么默认权重为1
[n,m] = size(G.Edges);x = length(unique(G.Edges.EndNodes));
W(1:x,1:x) = inf;W(logical(eye(size(W)))) = 0; % 初始化权重矩阵W,对角线赋值为0

if m ==1
    for i = 1:n
        W(G.Edges.EndNodes(i,1),G.Edges.EndNodes(i,2)) = 1; 
        
        try
            if class(G) == 'graph' % 如果为有向图，那么该权重矩阵为对称
                W(G.Edges.EndNodes(i,2),G.Edges.EndNodes(i,1)) = W(G.Edges.EndNodes(i,1),G.Edges.EndNodes(i,2));
            end
        end
    end
elseif m == 2
    for i = 1:n
        W(G.Edges.EndNodes(i,1),G.Edges.EndNodes(i,2)) = G.Edges.Weight(i);
        try
            if class(G) == 'graph' % 如果为有向图，那么该权重矩阵为对称
                W(G.Edges.EndNodes(i,2),G.Edges.EndNodes(i,1)) = W(G.Edges.EndNodes(i,1),G.Edges.EndNodes(i,2));
            end
        end
    end
end


% 建立距离矩阵Distend 父节点矩阵Parent 是否已访问矩阵Visit
% 初始化距离矩阵，默认初始距离为无穷,起始点距离为0
D(1,1:x) = inf;D(1,start) = 0;D_ = D; % D_为D的傀儡
% 初始化父节点矩阵为0
Parent = zeros(1,x);
% 初始化访问矩阵 为访问完成为0，访问完成为1
Visit = zeros(1,x);

% 计算起始点到每个点的最短距离
for i = 1:x
    [~,index] = min(D_);
    for j = 1:x
        if W(index,j) ~= inf && W(index,j) ~= 0 && Visit(j) == 0
            distent = W(index,j) + D(index);
            if distent < D(j)
                D(j) = distent;D_(j) = distent;
                Parent(j) = index; % 更新父节点
            end
        end     
    end
    Visit(index) = 1;D_(index) =inf; %这里把已访问过的节点距离设为inf方便之后查询D的最短路径时排除已访问过的节点
end
% 得到最短路径
d = D(End);
% 得到父节点们
% 初始化路径
P = [];
p = Parent(End);
for i = 1:x
    if any(P==start) == 0
        P(1,i) = p;
        p = Parent(p);
    end
end
P = fliplr(P);P(1,end+1) =End;
end

应用场景-最短路径问题
看一个应用场景和问题：



战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄

各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里

问：如何计算出G村庄到 其它各个村庄的最短距离?

如果从其它点出发到各个点的最短距离又是多少?.
迪杰斯特拉(Dijkstra)算法介绍
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
迪杰斯特拉(Dijkstra)算法过程
设置出发顶点为v，顶点集合V{v1,v2,vi…}，v到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,di…}，Dis集合记录着v到图中各顶点的距离(到自身可以看作0，v到vi距离对应为di)

从Dis中选择值最小的di并移出Dis集合，同时移出V集合中对应的顶点vi，此时的v到vi即为最短路径
更新Dis集合，更新规则为：比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为vi，表明是通过vi到达的)
重复执行两步骤，直到最短路径顶点为目标顶点即可结束

迪杰斯特拉(Dijkstra)算法最佳应用-最短路径


战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
问：如何计算出G村庄到 其它各个村庄的最短距离?
如果从其它点出发到各个点的最短距离又是多少?

思路图解

代码实现
package dijkstra;

import java.util.Arrays;


public class dijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        // 邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;    // 表示不可连接
        matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, N, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, N, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, N, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, N};
        // 创建Graph
        Graph graph = new Graph(vertex, matrix);
        // 测试
        graph.showGraph();

        // 测试迪杰斯特拉算法
        graph.dsj(6);

        // 查看结果
        graph.showDijkstra();
    }


}


class Graph {
    private char[] vertex; // 顶点数组
    private int[][] matrix;   // 邻接矩阵
    private VisitedVertex vv;   // 已经访问的结点集合

    // 构造器
    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    // 显示图的方法
    public void showGraph() {
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }


    /**
     * 迪杰斯特拉算法实现
     *
     * @param index 表示出发顶点对应的下标
     */
    public void dsj(int index) {
        vv = new VisitedVertex(vertex.length, index);
        update(index);  // 更新index顶点到周围顶点距离和前驱顶点
        for (int i = 0; i < vertex.length; i++) {
            index = vv.updateArr(); // 选择并返回新的访问顶点
            update(index);  // 更新index下标顶点到周围顶点的距离和周围顶点的前驱结点
        }
    }

    // 更新index下标顶点到周围顶点的距离和周围顶点的前驱结点
    private void update(int index) {
        int len = 0;
        // 根据遍历我们的邻接矩阵的matrix[index]行
        for (int j = 0; j < matrix[index].length; j++) {
            // len 含义是：出发顶点到index顶点的距离 + 从index顶点到j顶点的距离和
            len = vv.getDis(index) + matrix[index][j];
            // 如果j顶点没有被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
            if (!vv.in(j) && len < vv.getDis(j)) {
                vv.updatePre(j, index);  // 更新j顶点的前驱为index顶点
                vv.updateDis(j, len);    // 更新出发顶点到j顶点的距离
            }
        }
    }

    // 显示结果
    public void showDijkstra() {
        vv.show();
    }
}


// 已访问顶点集合
class VisitedVertex {
    // 记录各个顶点是否访问过，1表示访问过，0表示未访问，会动态更新
    public int[] already_arr;
    // 每个下标对应的值为前一个顶点下标，会动态更新
    public int[] pre_visited;
    // 记录出发顶点到其他所有顶点的距离，比如G为出发顶点，就会记录G到其他顶点的距离，会动态更新
    // 求的最短距离就会存放到dis
    public int[] dis;


    /**
     * @param length 表示顶点的个数
     * @param index  表示出发顶点对应的下标，比如G顶点，传入下标6
     */
    public VisitedVertex(int length, int index) {
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];

        // 初始化diss数组,全部填充为65535
        Arrays.fill(dis, 65535);
        this.already_arr[index] = 1;    // 设置出发顶点被访问过
        this.dis[index] = 0;    // 设置出发顶点的访问距离为0
    }

    /**
     * 功能：判断index顶点是否被访问过
     *
     * @param index 下标
     * @return 如果访问过，返回true，否则返回false
     */
    public boolean in(int index) {
        return already_arr[index] == 1;
    }

    /**
     * 功能：更新出发顶点到index的距离
     *
     * @param index 下标
     * @param len   长度
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 功能：更新pre顶点的前驱顶点为index的顶点
     *
     * @param pre   顶点
     * @param index 更新后顶点
     */
    public void updatePre(int pre, int index) {
        pre_visited[pre] = index;
    }

    /**
     * 功能：返回出发顶点到index顶点的距离
     *
     * @param index 顶点
     * @return 距离
     */
    public int getDis(int index) {
        return dis[index];
    }

    /**
     * 继续选择并返回新的访问结点，比如这里G访问完后，就是A点作为新的访问顶点(注意不是出发顶点)
     *
     * @return 尚未访问过的结点中值最小的
     */
    public int updateArr() {
        int min = 65535, index = 0;
        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }
        // 更新index被访问过
        already_arr[index] = 1;
        return index;
    }

    /**
     * 显示最后的结果，即将三个数组的情况输出
     */
    public void show() {
        System.out.println("===============================");
        // 输出already_arr
        for (int i : already_arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        // 输出pre_visited
        for (int i : pre_visited) {
            System.out.print(i + " ");
        }
        System.out.println();
        // 输出dis
        for (int i : dis) {
            System.out.print(i + " ");
        }
        System.out.println();

        //为了好看，最后的最短距离，处理一下
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "(" + i + ")");
            } else {
                System.out.println("N ");
            }
            count++;
        }
        System.out.println();
        System.out.println("===============================");
    }
}

路由算法有很多，本篇采用迪杰斯特拉最短路径法实现简单的路由算法。可能很多人一看到这个就会想到数据结构了，想到数据结构中必须要建立图的结构就很头疼，今天这种写法可以先不采用数据结构书上的写法，也可以实现相同的功能，毕竟，咱们的重点是要学习使用迪杰斯特拉算法，而不是构建图结构。
首先先来说一下迪杰斯特拉算法，从大概念上来说，该方法属于一种贪心算法，即当加进一个点后，算其相邻所有点的最短路径。详细过程如下：
如下图，要计算其中 点1 到其余各点的最短路径
 

 
总的计算过程见下表

表中红颜色代表当前行未加入到点集中的最小值，蓝颜色代表和上一个新加入点集中的点相邻的点，可能这样说还不是很清楚，就看下面的具体过程了。
第一步：初始化，把和 点1 相连的所有点的D（i）初始化，从图中可以看出，1和2、4、5相连，所以D（2）=10，D（4）=30，D（5）=100，点1和点3不直接相连，所以D（3）=65535，代表无穷大（在java里，可以用Integer.MAX_VALUE来表示无穷大）。由于现在点集中只有点1，所以找出刚才步骤1那行中D（i）最小的点，为点2（图中红色标明），将其加入到点集中。
第二步：此时点集中新加入了点2，则以点2为出发点，从图中看到只有点3与其相连，所以这一步中只需要更新D（3）即可，D（3）= min{D（3）， D（2）+ d（2,3）}，即D（3）= min{65535， 10+ 50} = 60，更新D（3）=60，其余点不变。这行更新完毕，发现未加入到点集中的D（4）最小，所以将点4加入到点集中。
第三步： 此时点集中新加入了点4，则以点4为出发点，从图中看到点3和点5与其相连，所以这一步需要更新D（3）和D（5）的值，D（3）= min{D（3）， D（4）+ d（4,3）} ，即D（3） = min{60, 30+20} = 50；D（5） = min{D（5）， D（4）+ d（4,5）} = min {100， 30 + 60} = 90。此时这一行其他数据不用变，此行更新完毕，找出未加入到点集中的 点3、点5 中的最小值，应该是点3，加入到点集中。
第四步，此时点集中新加入了点3，则以点3为出发点，发现点5与其相连，只需要更新D（5）即可。D（5） = min{D（5）， D（3）+ d（3,5）} = min {90， 50 + 10} = 60，此时这行更新完毕，只有最后一个 点5 未加入到点集中了，所以将其加入。
第五步，此时点集中新加入了点5，则以点5为出发点，发现根本没有点与其相连，甚好，此行就不用再更新了。
第六步，机智的我发现所有点都被包含在了点集中，所以本次迪杰斯特拉算法就到此结束了。
 
剩下的就是代码实现了。
用一个二维数组d[i][j]来存从第i个点到第j个点的路径权重，其中65535为无穷大； 用一个一维数组f[i]才表示从第1个节点到第i个节点的最短路径。
 

/* 
*王欢   12283013 
*实验四 编程实现路由算法 
*/ 
public class Dijkstra_Router { 
    public static void main(String[] args) throws IOException { 
        Scanner scanner = new Scanner(System.in); 
        int i, j; 
        int n = scanner.nextInt(); 
        //因为第0个单元我不用，所以就多开了两个空间 
        int[][] d = new int [n+2][n+2];  //二维矩阵存储点之间的距离 
        int []book = new int [n+2];    //标志数组，book[i]=0代表第i个点未在点集中，book[i]=1代表第i个点在点集中 
        int []f = new int[n+2];  //f[i]表示从第1个节点到第i个节点的最短路径 
        int min = 65535, min_pos = 0;   //最小值设置为65535，为了比较出最小值， min_pos表示当前步骤中最小路径值的小标 
        for (i=0;i<n+2;i++)   //初始化标志数组，并把第一个点添加到点集中，即book[1] = 1 
            book[i] = 0; 
        book[1] = 1; 
        for (i=1;i<=n;i++) 
            for (j=1;j<=n;j++) 
                d[i][j] = scanner.nextInt();   //读入二维矩阵，表示各个点的连接情况 
        for (i=2;i<=n;i++) 
            f[i] = d[1][i];   //按照上文所说的第一步进行初始化 
        System.out.println("运算过程："); 
        while (containsAllNodes(book, n)){ 
            min = 65535;  //每一步都要比较出最小值，所以记得在每一步的开始初始化一下最小值 
            for (i=2;i<=n;i++) 
                if (book[i] == 0 && f[i] < min){   //当第i个点未被加入到点集中 && f[i]<min 
                    min = f[i]; 
                    min_pos = i; 
                } 
            book[min_pos] = 1;  //找出当前步骤中最小值的位置为min_pos，即第min_pos个点加入到点集中，book[min_pos] = 1 
            for (i=1;i<=n;i++) 
                if (d[min_pos][i] != 65535)   //根据上文讲解，f[i] = min{ f[i], f[min_pos] + d[min_pos][i] }  这一步是最重要的，一定要理解。比如上面讲解的第二步中，D（3）= min{D（3）， D（2）+ d（2,3）}，类比一下 
                    f[i] = f[i] < (f[min_pos] + d[min_pos][i]) ? f[i] : (f[min_pos] + d[min_pos][i]);  
            for (i=1;i<=n;i++){ 
                System.out.print(f[i] + " ");  //打印本次运算结果 
            } 
            System.out.println(); 
        }
        System.out.println("最短路径： " + f[n]);  //整个过程全部结束了，打印出第1个点到第n个点的最短路径 
    }
    //判断是否所有点都被加入到点集中了 
    private static boolean containsAllNodes(int[] book, int n) { 
        for (int i=1;i<=n;i++){ 
            if (book[i] == 0) 
                return true; 
        } 
        return false; 
    } 
}
 


总结：如果可以熟练的手工算出那张动态表的话，就可以很好的理解迪杰斯特拉算法了。迪杰斯特拉本质上是一种动态规划，每次只能求出一个点到任意一个点的最短距离，而不是任意一个点到任意一个点的最短距离；同时又体现了贪心策略的思想，当一个新的点被加入到点集中时，下一步只需要更新与其直接相连（相邻）的点即可，而不是需要更新所有的点。至于使用什么语言来实现就都无所谓啦。还有如果需要记录最短路径所经过的节点，再增加相应数组编程实现即可。




个人github:  http://github.com/icodeu

       本例代码托管地址:https://github.com/icodeu/DijkstraForRouter

       个人微信号：qqwanghuan  只为技术交流


更多内容欢迎访问个人网站   http://icodeyou.com

1.基本思想
       迪杰斯特拉算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，用一个数组int[ ]dist保存起点到其余各点的最短路径距离，采用贪心算法的策略，每次遍历到起点距离最近且未访问过的顶点的邻接节点并不断更新dist数组，直到扩展到终点为止。
2.算法步骤

设置数组 int[ ]dist 保存起点到其余各点的最短路径距离，设置集合 s，用于保存图中已找到最短路径的顶点，并将起点加入集合s，作为集合s的初始化。
遍历集合s中的所有顶点的所有出边，找出权值最小的出边，根据最短路径终点延申出的最短出边可确定一条新的最短路径的思想，该权值最小出边所连接的未在集合s中顶点a的最短路径就是该路径。
顶点a的最短路径已找到，将顶点a加入集合s，并更新dist数组
重复上述2~3步骤，直到所有顶点都在集合s中

3.图示举例

4.代码实现
class Solution {
    /**
     *
     * @param map:图的邻接矩阵，如果两点直接不连通则对应的边的权值为{@code Integer.MAX_VALUE}
     * @param n:图的顶点总数
     */
    public int[] minimumEffortPath(int[][] map,int n) {
        //利用小顶堆路径排序，得到当前的最短路径
        PriorityQueue<int[]>queue=new PriorityQueue<int[]>
                (Comparator.comparingInt(o -> o[2]));
        //是否已经找到图中各顶点的最短路径
        boolean[]searched=new boolean[n];
        queue.add(new int[]{0,0});
        //起点到图中其他各点的最短距离
        int[]dist=new int[n];
        //初始化起点到其他各点的最短距离是无穷大
        Arrays.fill(dist,Integer.MAX_VALUE);
        //假设起点的顶点索引是0，起点到起点的最短路径是0
        dist[0]=0;
        while (!queue.isEmpty()){
            //小顶堆的根一定是最短路径
            int[]peek=queue.poll();
            int x=peek[0];
            int d=peek[1];
            //如果第二次遍历到顶点x，则跳过
            if(searched[x]){
                continue;
            }
            searched[x]=true;
            for(int i=0;i<n;i++){
                if(map[x][i]==Integer.MAX_VALUE){
                    continue;
                }
                int dd=map[x][i];
                if(d+dd<dist[i]){
                    dist[i]=d+dd;
                    //将可能的最短路径加入小顶堆
                    queue.add(new int[]{i,d+dd});
                }
            }
        }
        return dist;
    }
}