欢迎大家来到IT世界,在知识的湖畔探索吧!

暑假只有最开始的几天最有意思，考完试玩了几天就感觉到了无聊。抱着想要出去走走的心态，我制定了一个出行路线图，我在1号城市，想去看一看2，3，4，5号城市(每去一个城市都从1号城市出发)，一切准备就绪，但在做预算的时候遇到了一点小小的难题，出行图上每条边上的数字就是走这条路要花费的费用，怎样能算出花费最小的路径呢？Dijkstra，开始你的表演。

出行路线图

一.基本思想

Dijkstra算法是专门用于求单源最短路径的算法，它的思想也比较简单，先是找距源点最近的结点，把它放入自己的集合中，然后从第二个开始，在找集合以外的最短路径结点时，要先更新一下源点到其它结点的距离，比如当更新到某个结点k时，要把上一次找到的路径最短的结点temp看作一个”中转站”，求出源点到temp，再由temp到结点k的距离之和sum，把sum和源点直达k的距离相比较，如果直达的距离大于sum，把直达距离更新成sum。更新了一遍后，再在集合外的结点中寻找到达路径最短的结点。直到所有的结点都加入了集合为止。

以出行路线图为例，把1号城市到其它城市的最短距离存储到dist[]，与1号不存在边的结点初始化成无穷大，dist[1]=0，开始时集合中只有1。首先看1号城市直接能到达的城市中路径最短的城市，显而易见是城市2，所以dist[2]=3，把2加入集合；再进行更新。

1和2都在集合中，所以只需对3，4，5更新。1->3=4，而1->2->3=3+2=5，所以对3号城市不更新。对4号城市，1->4没有边，所以距离是无穷大，而1->2->4=3+7=10，所以将dist[4]更新为10。对5号城市，1->5没有边，所以距离是无穷大，而1->2->5=3+1=4，所以将dist[5]更新为4。

同理，等更新了一遍后，重新从未加入集合的结点中找出距离最短的结点，加入集合。之后再把新加入的结点当作”中转站”，比较并更新。最后所有结点都加入集合，表演也就结束了。最后的结果为

二.实现

1. 一开始我们要想办法存储图，创建集合，定义dist[]数组。之前我们已经讲过三种存储图的方法，我们选择第一种邻接矩阵法。表示集合的话，创建一个boolean类型的数组，初始时boolean[1]=true，即源点一开始就在集合中，其余都是false，表示该结点不在集合中，当结点加入集合时，对应的boolean变为true。

static int N=1000;
static int[][] map=new int[N+1][N+1];
static boolean[] flag=new boolean[N+1];
static int[] dist=new int[N+1];
static int INF=Integer.MAX_VALUE;

欢迎大家来到IT世界,在知识的湖畔探索吧!

2. 之后开始存储图，要输入图有n个结点，m条边。下面分别输入各边，最后输入源点，这里源点是1。

· 输入样例

欢迎大家来到IT世界,在知识的湖畔探索吧!5 7
1 2 3
1 3 4
2 3 2
2 5 1
3 5 2
2 4 7
4 5 5
1

        int n,m,u,v,w,source;
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        init(n);
        while(m-->0){
            u=sc.nextInt();
            v=sc.nextInt();
            w=sc.nextInt();
            map[u][v]=w;
        }
        source=sc.nextInt();

3. 数据准备好后，对dist[]数组进行初始化，dist[i]就是1到i的距离，1号城市开始就在集合中。

欢迎大家来到IT世界,在知识的湖畔探索吧!        for(int i=1;i<=n;i++){
            dist[i]=map[source][i];
        }
        flag[source]=true;

4. 在未加入集合的结点里找和源点最近的结点，如果没找到，说明已经都找完了，算法结束。否则加入集合，开始第五步。

5. 更新路径。以新加入集合的结点做”中转站”，判断是否通过中转能缩短距离，能的话更新路径，跳转到第四步。

       for(int i=1;i<=n-1;i++){
            int min=INF,temp=source;
            for(int j=1;j<=n;j++){
                if(!flag[j]&&dist[j]<min){
                    temp=j;
                    min=dist[j];
                }
            }
            if(temp==source)break;
            flag[temp]=true;
            for(int k=1;k<=n;k++){
                if(map[temp][k]<INF&&dist[k]>dist[temp]+map[temp][k]){
                    dist[k]=dist[temp]+map[temp][k];
                }
            }
        }

三.完整代码

import java.util.Scanner;

public class Dijkstra {
    static int N=1000;
    static int[][] map=new int[N+1][N+1];// adjacent matrix
    static boolean[] flag=new boolean[N+1];//Determines whether to store collections
    static int[] dist=new int[N+1];//An array of store shortest path distances
    static int INF=Integer.MAX_VALUE;
    public static void main(String[] args) {
        int n,m,u,v,w,source;
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();//Number of nodes is n
        m=sc.nextInt();//Number of edges is m
        init(n);
        while(m-->0){
            u=sc.nextInt();//start point 
            v=sc.nextInt();//destination
            w=sc.nextInt();//weight
            map[u][v]=w;//store
        }
        source=sc.nextInt();//source
        for(int i=1;i<=n;i++){
            dist[i]=map[source][i];//Determine the distance between the source point and other nodes
        }
        flag[source]=true;//Put the source point into the collection
        for(int i=1;i<=n-1;i++){
            int min=INF,temp=source;
            for(int j=1;j<=n;j++){//Find the closest node to the source point
                if(!flag[j]&&dist[j]<min){
                    temp=j;//Get the node's id
                    min=dist[j];//Get distance
                }
            }
            if(temp==source)break;//Find out all nodes,exit
            flag[temp]=true;//The newly selected node is added to the collection
            for(int k=1;k<=n;k++){
                if(map[temp][k]<INF&&dist[k]>dist[temp]+map[temp][k]){
                    dist[k]=dist[temp]+map[temp][k];//Update path condition
                }
            }
        }
        for(int i=1;i<=n;i++){
            System.out.println("从城市"+source+"到城市"+i+"的距离为"+dist[i]);
        }
    }
    private static void init(int n){//Initialize the matrix
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j){
                    map[i][j]=0;
                }else {
                    map[i][j]=INF;
                }
            }
        }
    }
}

如果您觉得这篇文章对您有所帮助，欢迎关注我的微信公众号–【悬浮流星】，阅读更多的类似文章。如果您发现该文章有错误或不足之处，也欢迎批评指正。