前言

​ 求最短路径的算法有很多种，本文介绍其中的两种算法——Floyd与Dijkstra算法

​ （本文若有不正确的地方望大佬们多多指正Orz）

【本文优先发布于我的个人博客网站www.226yzy.com ,转载请注明出处】

1. Floyd算法

​ 首先通过HDU2544最短路这道题引入最短路径这一问题。

（题目可通过链接查看或见下方截图）

HDU2544最短路题目截图

（一）路径记录及预处理

​ 上题中样例过于简单，但值得注意的是上题中所给的线路时间是无向的，即该路线来回时间一致。以第二组为例，记录路线时间如下表。

1号点 2号点 3号点
1号点 0 5 2
2号点 5 0 5
3号点 2 5 0

​ 反之，若有向（当然上题为无向）则记录如下表

1号点 2号点 3号点
1号点 0 5 ∞
2号点 ∞ 0 5
3号点 2 ∞ 0

​ 处理上，无论有向还是无向，对于某一点到自身距离记录为0，除此之外，若某一点到另一点并无路径则记录为∞，代码上可用一个非常大的数代表（例如下文代码用999999999代表，也可通过函数调取如int型或long型的最大值）。

该片段代码大致如下(本文暂以java代码作为演示)，下示代码中T1为无向时的记录方法，T2为无向时的记录方法，本题为无向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
			int n=sc.nextInt(),m=sc.nextInt(),s,e;
            //根据题目描述，n代表有几个地点，m代表有几条输入路径，s代表该路径起点，e代表该路径目的地
			int[][]map=new int[n][n];//记录路径的二维数组
			if(n==0&&m==0)break;//根据题目代表所有输入结束
            //初始化记录路径的数组
			for(int i=0;i<n;i++)
				  for(int j=0;j<n;j++)
					  if(i==j)map[i][j]=0;
					  else map[i][j]=999999999;
			while(m-->0){
				s=sc.nextInt()-1;e=sc.nextInt()-1;
//				map[s][e]=sc.nextInt();//T1：有向时的记录方法
				map[s][e]=map[e][s]=sc.nextInt();//T2：无向时的记录方法
			}

（二）Floyd核心代码

​ Floyd的核心代码较为简单，只有简单的几行，代码如下

1
2
3
4
5
      for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];

（核心代码解读待续……）

（三）完整代码（不含路径）

综上,完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n=sc.nextInt(),m=sc.nextInt(),s,e;
            int[][]map=new int[n][n];
            if(n==0&&m==0)break;
            for(int i=0;i<n;i++)
                  for(int j=0;j<n;j++)
                      if(i==j)map[i][j]=0;
                      else map[i][j]=999999999;
            while(m-->0){
                s=sc.nextInt()-1;e=sc.nextInt()-1;
//                map[s][e]=sc.nextInt();
                map[s][e]=map[e][s]=sc.nextInt();
            }                
            for(int k=0;k<n;k++)
               for(int i=0;i<n;i++)
                  for(int j=0;j<n;j++)
                     if(map[i][j]>map[i][k]+map[k][j])
                        map[i][j]=map[i][k]+map[k][j];        
            System.out.println(map[0][n-1]);
            //打印总表
//            System.out.println();
//            for(i=0;i<n;i++) {
//                for(j=0;j<n;j++) {
//                    System.out.print(map[i][j]+"\t");
//                }
//                System.out.println();     
//            }
                  
        }
    }
}

2. Dijkstra算法

（一）路径记录及预处理

​ 与Floyd算法的处理基本一致，具体见上文

​ 不同的是Dijkstra算法还需要增加一个一维数组来存储选定的起始点到其余的各个顶点的初始路程，该数组的名称本文定义为dis。并另建一个一维数组vis来记录数组dis对应的点是否已经找到与起始点的最短路径，0表示还未找到，1表示已找到。

​ 对于数组vis建立完后，还要进行预处理,就是先将起始点对应的值标为1

（二）核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
      int u=1,min;
vis[s]=1;
for(int i=1;i<=n;i++)
	dis[i]=map[s][i];
for(int i=1;i<=n;i++){
	min=inf;
	for(int j=1;j<=n;j++)
		if(vis[j]==0&&dis[j]<min){
			min=dis[j];u=j;
		}	
	vis[u]=1;
    for(int j=1;j<=n;j++)
	   if(map[u][j]<inf)
		 if(dis[j]>dis[u]+map[u][j]) {
			 dis[j]=dis[u]+map[u][j];
			 p[j]=u;
		 }		 
}

（核心代码解读待续……）

（三）完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.*;
public class 最短路径{
	static int n=26,inf=99999999;
	static int[]dis=new int[n+1],vis=new int[n+1],p=new int[n+1],YY=new int[n+1];
	static int[][] map=new int[n+1][n+1];
	public static void main(String[] args){
		for(int i=1;i<=n;i++)
	        for(int j=1;j<=n;j++)
	            map[i][j]=(i==j?0:inf);
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入起始点、目的地、距离。以起始点为0作为结束标志");
		int[][]t=new int[n+1][n+1];
		while(sc.hasNext()) {
			int s=sc.nextInt();
			if(s==0)break;
			int e=sc.nextInt(),d=sc.nextInt();
			map[s][e]=map[e][s]=d;
			t[s][e]=t[e][s]=d;
		}
		yzy(22);
		System.out.println();
		for(int i=1;i<=n;i++){
			System.out.print(i+"\t");
		}
		System.out.println();
		for(int i=1;i<=n;i++){
			System.out.print(YY[i]+"\t");
		}
	}
	static void yzy(int s) {		
		int u=1,min;
		vis[s]=1;
		for(int i=1;i<=n;i++)
			dis[i]=map[s][i];
		for(int i=1;i<=n;i++){
			min=inf;
			for(int j=1;j<=n;j++)
				if(vis[j]==0&&dis[j]<min){
					min=dis[j];u=j;
				}	
			vis[u]=1;
		    for(int j=1;j<=n;j++)
			   if(map[u][j]<inf)
				 if(dis[j]>dis[u]+map[u][j]) {
					 dis[j]=dis[u]+map[u][j];
				 }		 
		}		
	}

3. 记录路径

​ 上文中的代码仅实现了给出最短路径的长度，但为给出具体路径，对于这个缺点下文进行相应的改进

（一）Dijkstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package 数学建模;

import java.util.*;
public class 最短路径{
	static int n=26,inf=99999999;
	static int[]dis=new int[n+1],vis=new int[n+1],p=new int[n+1],YY=new int[n+1];
	static int[][] map=new int[n+1][n+1];
	public static void main(String[] args){
		for(int i=1;i<=n;i++)
	        for(int j=1;j<=n;j++)
	            map[i][j]=(i==j?0:inf);
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入起始点、目的地、距离。以起始点为0作为结束标志");
		int[][]t=new int[n+1][n+1];
		while(sc.hasNext()) {
			int s=sc.nextInt();
			if(s==0)break;
			int e=sc.nextInt(),d=sc.nextInt();
			map[s][e]=map[e][s]=d;
			t[s][e]=t[e][s]=d;
		}
		yzy(22);
		ff(22);
		System.out.println();
		for(int i=1;i<=n;i++){
			System.out.print(i+"\t");
		}
		System.out.println();
		for(int i=1;i<=n;i++){
			System.out.print(YY[i]+"\t");
		}
	}
	static void yzy(int s) {		
		int u=1,min;
		vis[s]=1;
		for(int i=1;i<=n;i++)
			dis[i]=map[s][i];
		for(int i=1;i<=n;i++){
			min=inf;
			for(int j=1;j<=n;j++)
				if(vis[j]==0&&dis[j]<min){
					min=dis[j];u=j;
				}	
			vis[u]=1;
		    for(int j=1;j<=n;j++)
			   if(map[u][j]<inf)
				 if(dis[j]>dis[u]+map[u][j]) {
					 dis[j]=dis[u]+map[u][j];
					 p[j]=u;
				 }		 
		}
		
	}
	static void ff(int s) {
		int j;
	    Stack<Integer> q=new Stack<Integer>();             
	    for(int i=1;i<=n;i++)            
	    {
	        j=i;
	        while(p[j]>0)      
	        {
	            q.add(j);          
	            j=p[j];          
	        }
	        q.push(j);
	        System.out.printf("起始点与目的地:%d-->%d\t路径长度:%d\t具体路径: %d ",s,i,dis[i],s);
	        while(!q.empty())       
	        {
	            System.out.printf(" --> %d",q.peek());
	            YY[q.peek()]++;
	            q.pop();            
	        }
	        System.out.println();
	    }
	}
}

示例题目

题目详情 - L2-001 紧急救援 (25 分) (pintia.cn)

PTA上的这道天梯赛真题还是挺适合练手的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=510;
const int inf=1e7;
int mp[M][M],vis[M],dis[M],city[M],path[M],tt[M],ss[M],ans[M],n,m,s,d,u,v,w,kk=0;
int into() {
	for(int i=0; i<=n; i++) {
		for(int j=i+1; j<=n; j++) {
			mp[i][j]=mp[j][i]=inf;
		}
	}
}
void dij(int x) {
	for(int i=0;i<n;i++){
		ss[i]=city[i];
		tt[i]=1;
	}
	int min,next=x;
	for(int i=0; i<n; i++) {
		dis[i]=mp[x][i];
	}
	vis[x]=1;
	for(int i=1; i<n; i++) {
		min=inf;
		for(int j=0; j<n; j++) {
			if(!vis[j]&&dis[j]<min) {
				min=dis[j];
				next=j;	
			}
		 else if(!vis[j]&&dis[j]==min) {
				if(city[j]>city[next]) {
					min=dis[j];
					next=j;	
				}				
			}
		}
		vis[next]=1;
		for(int j=0; j<n; j++) {
			if(!vis[j]&&dis[j]>dis[next]+mp[next][j]) {
				dis[j]=dis[next]+mp[next][j];
				path[j]=next;
				ss[j]=ss[next]+city[j];
				tt[j]=tt[next];
			} else if(!vis[j]&&dis[j]==dis[next]+mp[next][j]) {
				if(ss[j]<ss[next]+city[j]){
					dis[j]=dis[next]+mp[next][j];
					ss[j]=ss[next]+city[j];
					path[j]=next;
				}				
				tt[j]+=tt[next];
			}
		}
	}
}
void ppath(int e) {
	stack<int>q;
	int k=e;
	while(path[k]) {
		q.push(k);
		k=path[k];
	}
	q.push(k);
	while(!q.empty()) {
		int vv=q.top();
		ans[++kk]=vv;
		q.pop();
	}
}
int main() {
	cin>>n>>m>>s>>d;
	into();
	for(int i=0; i<n; i++) {
		cin>>city[i];
	}
	while(m--) {
		cin>>u>>v>>w;
		mp[u][v]=mp[v][u]=w;
	}
	dij(s);
	ppath(d);
	cout<<tt[d]<<" "<<ss[d]+city[s]<<endl;
	cout<<s;
	for(int i=1; i<=kk; i++) {
		cout<<" "<<ans[i];
	}
}

4.其它语言代码

（一）Floyd算法matlab代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
a=zeros(6); %矩阵初始化
%路径录入，可根据实际情况修改
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a';
a(find(a==0))=inf;
n=length(a);
for k=1:n
    a(k,k)=0;
end
for k=1:n
    for i=1:n
        for j=1:n
            if a(i,k)+a(k,j)<a(i,j)
                a(i,j)=a(i,k)+a(k,j); 
            end 
        end
    end
end
a