單源最短路徑問題，即在圖中求出給定頂點到其它任一頂點的最短路徑。在弄清楚如何求算單源最短路徑問題之前，必須弄清楚最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。
一、最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)
該性質(zhì)描述為：如果p(i,j)={vi....vk..vs...vj}是從頂點i到j(luò)的最短路徑，k和s是這條路徑上的中間頂點，那么p(k,s)必定是從k到s的最短路徑。下面證明該性質(zhì)的正確性。
假設(shè)p(i,j)={vi....vk..vs...vj}是從頂點i到j(luò)的最短路徑，則有p(i,j)=p(i,k)+p(k,s)+p(s,j)。而p(k,s)不是從k到s的最短距離，那么必定存在另一條從k到s的最短路徑p'(k,s)，那么p'(i,j)=p(i,k)+p'(k,s)+p(s,j)<p(i,j)。則與p(i,j)是從i到j(luò)的最短路徑相矛盾。因此該性質(zhì)得證。
二、dijkstra算法
dijkstra提出按各頂點與源點v間的路徑長度的遞增次序，生成到各頂點的最短路徑的算法。既先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從源點v 到其它各頂點的最短路徑全部求出為止。
對于下圖：
運行結(jié)果：
從0出發(fā)到0的最短路徑為：0-->0
從0出發(fā)到1的最短路徑為：0-->1
從0出發(fā)到2的最短路徑為：0-->3-->2
從0出發(fā)到3的最短路徑為：0-->3
從0出發(fā)到4的最短路徑為：0-->3-->2-->4
=====================================
從0出 發(fā)到0的最短距離為：0
從0出 發(fā)到1的最短距離為：10
從0出 發(fā)到2的最短距離為：50
從0出 發(fā)到3的最短距離為：30
從0出 發(fā)到4的最短距離為：60
=====================================
|
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
|
public class dijkstra { static int m=10000;//(此路不通) public static void main(string[] args) { // todo auto-generated method stub int[][] weight1 = {//鄰接矩陣 {0,3,2000,7,m}, {3,0,4,2,m}, {m,4,0,5,4}, {7,2,5,0,6}, {m,m,4,6,0} }; int[][] weight2 = { {0,10,m,30,100}, {m,0,50,m,m}, {m,m,0,m,10}, {m,m,20,0,60}, {m,m,m,m,0} }; int start=0; int[] shortpath = dijsktra(weight2,start); for(int i = 0;i < shortpath.length;i++) system.out.println("從"+start+"出發(fā)到"+i+"的最短距離為："+shortpath[i]); } public static int[] dijsktra(int[][] weight,int start){ //接受一個有向圖的權(quán)重矩陣，和一個起點編號start（從0編號，頂點存在數(shù)組中） //返回一個int[] 數(shù)組，表示從start到它的最短路徑長度 int n = weight.length; //頂點個數(shù) int[] shortpath = new int[n]; //存放從start到其他各點的最短路徑 string[] path=new string[n]; //存放從start到其他各點的最短路徑的字符串表示 for(int i=0;i<n;i++) path[i]=new string(start+"-->"+i); int[] visited = new int[n]; //標記當前該頂點的最短路徑是否已經(jīng)求出,1表示已求出 //初始化，第一個頂點求出 shortpath[start] = 0; visited[start] = 1; for(int count = 1;count <= n - 1;count++) //要加入n-1個頂點 { int k = -1; //選出一個距離初始頂點start最近的未標記頂點 int dmin = integer.max_value; for(int i = 0;i < n;i++) { if(visited[i] == 0 && weight[start][i] < dmin) { dmin = weight[start][i]; k = i; } } system.out.println("k="+k); //將新選出的頂點標記為已求出最短路徑，且到start的最短路徑就是dmin shortpath[k] = dmin; visited[k] = 1; //以k為中間點，修正從start到未訪問各點的距離 for(int i = 0;i < n;i++) { // system.out.println("k="+k); if(visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]){ weight[start][i] = weight[start][k] + weight[k][i]; path[i]=path[k]+"-->"+i; } } } for(int i=0;i<n;i++) system.out.println("從"+start+"出發(fā)到"+i+"的最短路徑為："+path[i]); system.out.println("====================================="); return shortpath; }} |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/gloria0610/article/details/23742799
