一、Dijkstra算法(貪心地求最短距離的算法)

　　在此算法中，我按照自己的理解去命名，理解起來會輕松一些。

　　

#define MAXSIZE 100 #define UNVISITED 0 #define VISITED 1 #define INFINITY 66666typedef struct tool {int visited[MAXSIZE];/*是否已訪問的數組,visited[i]表示頂點i已經訪問，也就是到頂點i的最短距離已求出*/int known_shortest_distance[MAXSIZE];/*已知的最短距離數組。known_shortest_distance[i]代表從V0到Vi的最短距離*/int previous_vertex[MAXSIZE];/*previous_vertex[i]=j,代表：在從V0到Vi的最短路徑上，頂點i的前一個頂點是頂點j*/ } Tool;typedef struct gragh {int num_of_vertexes;int adjacent_matrix[MAXSIZE][MAXSIZE]; } Gragh;void init_tool(Gragh g, Tool &t) {int i = 0;for(i = 0; i < g.num_of_vertexes; i++) {t.visited[i] = UNVISITED;t.known_shortest_distance[i] = g.adjacent_matrix[0][i];t.previous_vertex[i] = 0;} }void dijstra_shortest_distance(Gragh g, Tool &t) {int i, j, x; //循環變量int min_distance, x_index;/*min_distance存儲的是當前已知的最短距離數組中從V0到Vx最小的距離;x_index存儲的Vx的下標*/init_tool(g, t);for(i = 0; i < g.num_of_vertexes; i++) {min_distance = INFINITY;for(x = 0; x < g.num_of_vertexes; x++) {if(!t.visited[x] && t.known_shortest_distance[x] < min_distance) {min_distance = t.known_shortest_distance[x];x_index = x;}}/*通過上面一個循環，最短距離數組中的最小值就是min_distance;該頂點的下標就是x_index;在當前沒有訪問且以V0為起點距離最短的頂點中，這個點的下標就是x_index.*/t.visited[x_index] = VISITED;for(j = 0; j < g.num_of_vertexes; j++) {if(!t.visited[j] && (min_distance + g.adjacent_matrix[x_index][j] < t.known_shortest_distance[j])) {t.known_shortest_distance[j] = min_distance + g.adjacent_matrix[x_index][j];t.previous_vertex[j] = x_index;}}}}

如果要求任意兩點之間的最短距離：只需在外層加一層循環，把最短距離數組和previous_vertex數組變成二維數組即可。?

?

輸出從V0到Vi的最短距離和完整路徑：

#include<stack> void print_path(Tool &t, int dest) {int i = dest;stack<int> s;cout << "從V0到V" << i << "的最短距離:" << t.known_shortest_distance[i] << endl;while(t.previous_vertex[i] != 0) {s.push(t.previous_vertex[i]);i = t.previous_vertex[i];}cout << "從V0到V" << i << "的路徑:";cout<<"V0";while(!s.empty()) {cout << "->V" << s.top();s.pop();}cout << "->V" << dest; }

?

?

?

一、Floyd算法(不管三七二十一，先把整個圖中任意兩點的最短距離求出再說)

?　　核心思想：對圖中任意兩個頂點(即下面代碼中的j和k),如果能在其他頂點中(也就是下面代碼中的i，在原始版本中，i和j,k可以相同)找到一個頂點i，使得頂點j到頂點i的距離加上頂點i的距離到頂點k的距離比直接從頂點j到頂點k的距離短，那么，就修改頂點j到頂點k的距離。

typedef struct floyd_tool {int known_shortest_distance[MAXSIZE][MAXSIZE];/*已知的最短距離數組。known_shortest_distance[i][j]代表從Vi到Vj的最短距離*/int path_matrix[MAXSIZE][MAXSIZE];/*path_matrix[i][j]=k,代表：在從Vi到Vj的最短路徑上，要經過頂點k;用k代替i,直到path_matrix[k][j]=j*/ } FloydTool;void init_floyd_tool(FloydTool &ft, Gragh g) {for(int i = 0; i < g.num_of_vertexes; i++) {for(int j = 0; j < g.num_of_vertexes; j++) {ft.known_shortest_distance[i][j] = g.adjacent_matrix[i][j];ft.path_matrix[i][j] = j;}} }void floyd_shortest_distance(Gragh g,FloydTool &ft) {init_floyd_tool(ft,g);for(int i = 0;i < g.num_of_vertexes; i++){for(int j = 0;j < g.num_of_vertexes;j++){for(int k = 0;k < g.num_of_vertexes;k++){if(ft.known_shortest_distance[j][k] >ft.known_shortest_distance[j][i] + ft.known_shortest_distance[i][k]){ft.known_shortest_distance[j][k] =ft.known_shortest_distance[j][i] + ft.known_shortest_distance[i][k];ft.path_matrix[j][k] = ft.path_matrix[j][i];}}}} }

?

?

改進版：

改進依據：由上面初始版本的思想可知，對于任意兩個頂點j和頂點k，如果頂點j和頂點i是同一個，那么，最里面一層的比較相當于是D和0+D在比，顯然，這是沒必要的。或者，如果j和i不相等，但是i不是j的鄰接點，那么j到i的距離就是“無窮大”，很顯然，通過這個橋梁i是不可能縮短j到k的距離的。所以，有了第一個if；同理，第二個if也是這么來的。然后，初始版本中，最里面兩層循環的循環變量都是從0開始的，但是因為我們考慮的是無向圖，j到k的距離和k到j的距離是一樣的，所以，我在改進版本中減去了重復求k到j的距離。

void floyd_shortest_distance(Gragh g,FloydTool &ft) {init_floyd_tool(ft,g);for(int i = 0;i < g.num_of_vertexes; i++){for(int j = 0;j < g.num_of_vertexes;j++){if(j == i || ft.known_shortest_distance[j][i] == INFINITY)continue;for(int k = j + 1;k < g.num_of_vertexes;k++){if(k == i || ft.known_shortest_distance[k][i] == INFINITY)continue;if(ft.known_shortest_distance[j][k] >ft.known_shortest_distance[j][i] + ft.known_shortest_distance[i][k]){ft.known_shortest_distance[j][k] =ft.known_shortest_distance[j][i] + ft.known_shortest_distance[i][k];ft.path_matrix[j][k] = ft.path_matrix[j][i];}}}} }

?

輸出最短距離和完整路徑：

void print_path(FloydTool &ft,int orig,int dest) {cout << "從V"<<orig<<"到V"<<dest<< "的最短距離:" << ft.known_shortest_distance[orig][dest] << endl;cout << "從V"<<orig<<"到V"<<dest<<"的路徑:";cout<<"V"<<orig;while(ft.path_matrix[orig][dest] != dest){cout<<"->V"<<ft.path_matrix[orig][dest];orig = ft.path_matrix[orig][dest];}cout << "->V" << dest; }

?

轉載于:https://www.cnblogs.com/fuzhihong0917/p/6262811.html

總結

以上是生活随笔為你收集整理的数据结构——图——最短路径DF算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。