图的最短路径：Dijkstra算法与Floyd算法（Java实现）_贪心算法求解最小路径

对于网图（边有权值的图），最短路径指的是两顶点之间经过的边上权值之和最小的路径

网如下图，求其最短路径

Dijkstra算法

是贪心算法的一种实现，按路径长度递增的次序产生最短路径的算法
基本思想

1. 将起始顶点A记录为已访问，并找到它最小权值的邻接边和对应的邻接顶点B，此时，这两个顶点间的最短路径就是这条邻接边
2. 对于B的最短邻接边对应的顶点C，判断起始顶点A与其之间的边是否比A-B-C更短，哪个更短哪个就是A到C之间的最短路径
3. 对于C的最短邻接边对应的顶点D，判断A-D、A-B-D、A-B-C-D哪个更短，哪个更短哪个就是A到D之间的最短路径
4. 重复上述操作，直到遍历到终点，此时A到其他所有点的最短路径都确定了

算法实现

	public static void dijkstra(Graph<?> G, int begin)              //x表示最短路径的起点
	{
		
		
		int[] shortPath = new int[G.getNumOfVertexes()];            //用于存储最短路径下标,值是角标位的前一个顶点
		int[] shortPathLength = new int[G.getNumOfVertexes()];      //用于存储最短路径权值和
		
		boolean[] isVisited = new boolean[G.getNumOfVertexes()];            //用于识别是否已经求得起点到角标位的最短路径
		
		//初始化上述三个数组
		for(int i = 0; i < G.getNumOfVertexes(); i++)
		{
			shortPath[i] = 0;                          //开始时最短路径下标均为0
			shortPathLength[i] = G.edges[begin][i];    //存储起点的邻接边的权值
			isVisited[i] = false;                          //全部为未知
		}
		
		
		
		//求起始顶点到每个顶点i的最短路径
		int k = 0;   //用于记录最短路径的顶点
		
		//起始顶点到第i个顶点的最短路径
		for(int i = 0; i < G.getNumOfVertexes(); i++)
		{
			int min = Graph.INFINITY;      //初始化离起始顶点最近的距离
			
			//找出离begin最近的顶点
			for(int j = 0; j < G.getNumOfVertexes(); j++)
			{
				if(shortPathLength[j] < min && !isVisited[j])
				{
					min = shortPathLength[j];
					k = j;
				}
			}
			
			isVisited[k] = true;
			
			//起始顶点到k的邻接顶点n是否有更短的路径
			for(int n = 0; n < G.getNumOfVertexes(); n++)
			{
				//判断从起始顶点到n是否有更短的路径，更新最短路径
				if(!isVisited[n] && (min + G.edges[k][n]) < shortPathLength[n])
				{
					shortPathLength[n] = min + G.edges[k][n];
					shortPath[n] = k;
					
				}
					
			}
		}
		
		System.out.println(Arrays.toString(shortPath));        
		System.out.println(Arrays.toString(shortPathLength));
		System.out.println(Arrays.toString(isVisited));
		
		
	}
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

对上述代码进行测试(图的邻接矩阵结构参见图的数据结构：邻接矩阵（Java实现）)

public static void main(String[] args) 
	{
		String Vertexes[] = {"V0", "V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8"};

		
		//创建图对象
		Graph<String> graph = new Graph<>(Vertexes.length);
		//循环的添加顶点
		for(String vertex: Vertexes) {
			graph.insertVertex(vertex);
		}
		
		
		//边的关系
		graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 5);
		graph.insertEdge(1, 2, 3);
		graph.insertEdge(1, 3, 7);
		graph.insertEdge(1, 4, 5);
		graph.insertEdge(2, 4, 1);
		graph.insertEdge(2, 5, 7);
		graph.insertEdge(3, 4, 2);
		graph.insertEdge(3, 6, 3);
		graph.insertEdge(4, 5, 3);
		graph.insertEdge(4, 6, 6);
		graph.insertEdge(4, 7, 9);
		graph.insertEdge(5, 7, 5);
		graph.insertEdge(6, 7, 2);
		graph.insertEdge(6, 8, 7);
		graph.insertEdge(7, 8, 4);
		

		
		
		//显示邻结矩阵
		//graph.showGraph();
		
		//寻找最小路径
		dijkstra(graph, 0);

	}
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

结果为

shortpath：  [0, 0, 1, 4, 2, 4, 3, 6, 7]  //short[8] = 7,表示V0到V8的最短路径中，V8的上一个顶点是V7
                                          //V0-V8:V8-V7-V6-V3-V4-V2-V1-V0 
shortpathlength： [0, 1, 4, 7, 5, 8, 10, 12, 16] //shortpathlength[8] = 16表示V0到V8最短路径长为16
isVisited[] ：[true, true, true, true, true, true, true, true, true] //所有顶点均被测试过
1
2
3
4

算法分析

• 由循环嵌套，可以得到一个顶点到其他所有顶点的最短路径的时间复杂度为O(n²)，那么所有顶点到其他顶点的最短路径为O(n³)

Floyd算法

基本思想

1. 对于两个顶点A-B 的最短路径，分别使用所有顶点进行中转A-X-B，找到其中的最小值作为A-B 的最短路径
2. 将A、B扩大到整个顶点集合，利用1中已经得到的最短路径就得到了所有顶点到所有顶点的最短路径

算法实现

 //存储最短路径下标：顶点i与顶点j之间最短路径由顶点shortPath[i][j]中转
	static int[][] shortPath;
	
	//存储顶点与顶点的最短路径权值
	static int[][] shortPathLength;
	
	public static void floyd(Graph<?> g)
	{
		shortPath = new int[g.getNumOfVertexes()][g.getNumOfVertexes()];
		
		shortPathLength = new int[g.getNumOfVertexes()][g.getNumOfVertexes()];
		
		//初始化这两个矩阵
		for(int i = 0; i < g.getNumOfVertexes(); i++)
			for(int j = 0; j < g.getNumOfVertexes(); j++)
			{
				shortPath[i][j] = j;  
				shortPathLength[i][j] = g.edges[i][j];
			}
		
		//求顶点n到顶点m之间最短路径及权值
		for(int k = 0; k < g.getNumOfVertexes(); k++)           //k为中转顶点
			for(int n = 0; n < g.getNumOfVertexes(); n++)       //n为起始顶点
				for(int m = 0; m < g.getNumOfVertexes(); m++)   //m为终止顶点
					{
						//判断中转顶点是否缩短了两点之间的权值
						if(shortPathLength[n][m] > shortPathLength[n][k] + shortPathLength[k][m])
						{
							//缩短，记录最短权值和中转顶点
							shortPathLength[n][m] = shortPathLength[n][k] + shortPathLength[k][m];
							shortPath[n][m] = shortPath[n][k];  //不是k，因为可能要经过更多的中转点 
							
						}	
					}
		
		
			

		
	}
	
	//获取Floyd算法下某图中两个顶点间的最短路径及相关权值
	public static void getShortPath(Graph<?> G, int[][] shortPath, int[][] shortPathLength, int a, int b)
	{
		//显示shortPath矩阵
		for(int[] x: shortPath)
			System.out.println(Arrays.toString(x));
		
		//显示shortPathLength矩阵
		for(int[] x: shortPathLength)
			System.out.println(Arrays.toString(x));
		
		System.out.println("这两个顶点间的最短路径总权值为：" + shortPathLength[a][b]);
		System.out.println("这两个顶点间的最短路径为：");
		System.out.print(G.getValueByIndex(a)+" --> ");
		int k = a;
		while(shortPath[k][b] != b)
		{
			System.out.print(G.getValueByIndex(shortPath[k][b])+" --> ");
			k = shortPath[k][b];
		}
		System.out.print(G.getValueByIndex(b));
	}
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

测试代码

	public static void main(String[] args) 
	{
		String Vertexes[] = {"V0", "V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8"};

		
		//创建图对象
		Graph<String> graph = new Graph<>(Vertexes.length);
		//循环的添加顶点
		for(String vertex: Vertexes) {
			graph.insertVertex(vertex);
		}
		
		
		//边的关系
		graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 5);
		graph.insertEdge(1, 2, 3);
		graph.insertEdge(1, 3, 7);
		graph.insertEdge(1, 4, 5);
		graph.insertEdge(2, 4, 1);
		graph.insertEdge(2, 5, 7);
		graph.insertEdge(3, 4, 2);
		graph.insertEdge(3, 6, 3);
		graph.insertEdge(4, 5, 3);
		graph.insertEdge(4, 6, 6);
		graph.insertEdge(4, 7, 9);
		graph.insertEdge(5, 7, 5);
		graph.insertEdge(6, 7, 2);
		graph.insertEdge(6, 8, 7);
		graph.insertEdge(7, 8, 4);
		

		
		
		//显示邻结矩阵
		//graph.showGraph();
		
		floyd(graph);
		getShortPath(graph, shortPath, shortPathLength, 0, 8);
		
	}
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

结果为

[0, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2, 2, 2, 2]
[1, 1, 2, 4, 4, 4, 4, 4, 4]
[4, 4, 4, 3, 4, 4, 6, 6, 6]
[2, 2, 2, 3, 4, 5, 3, 3, 3]
[4, 4, 4, 4, 4, 5, 7, 7, 7]
[3, 3, 3, 3, 3, 7, 6, 7, 7]
[6, 6, 6, 6, 6, 5, 6, 7, 8]
[7, 7, 7, 7, 7, 7, 7, 7, 8]

[0, 1, 4, 7, 5, 8, 10, 12, 16]
[1, 0, 3, 6, 4, 7, 9, 11, 15]
[4, 3, 0, 3, 1, 4, 6, 8, 12]
[7, 6, 3, 0, 2, 5, 3, 5, 9]
[5, 4, 1, 2, 0, 3, 5, 7, 11]
[8, 7, 4, 5, 3, 0, 7, 5, 9]
[10, 9, 6, 3, 5, 7, 0, 2, 6]
[12, 11, 8, 5, 7, 5, 2, 0, 4]
[16, 15, 12, 9, 11, 9, 6, 4, 0]

这两个顶点间的最短路径总权值为：16
这两个顶点间的最短路径为：
V0 --> V1 --> V2 --> V4 --> V3 --> V6 --> V7 --> V8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

算法是有效的
算法分析

• 三重循环的先后顺序对结果没有影响
• 由于三重循环，时间复杂度为O(n³)
• 要求所有顶点到所有顶点的最短路径，Floyd算法更方便