圖的最短路徑
- 【對于非網(wǎng)圖】沒有邊上的權(quán)值，它的最短路徑就是兩個頂點之間經(jīng)過的邊數(shù)目最少的路徑。
- 【對于網(wǎng)圖】最短路徑是指兩頂點之間經(jīng)過的邊上權(quán)值之和和最少的路徑，并且稱路徑上的第一個頂點是源點，最后一個頂點是終點忍疾。
-
非網(wǎng)圖可以看做所有邊的權(quán)值都為
1的網(wǎng)圖。 - 求解最短路徑的方法有兩種：
- 從某個源點到其余各個頂點的最短路徑問題：迪杰斯特拉(Dijkstra)算法谨朝。
- 圖中所有到多有頂點的最短路徑問題：弗洛伊德(Floyd)算法
本文所用圖
一卤妒、迪杰斯特拉(Dijkstra)算法
迪杰斯特拉(Dijkstra)算法核心：按照路徑長度遞增的次序產(chǎn)生最短路徑。
迪杰斯特拉(Dijkstra)算法步驟：（求圖中v0到v8的最短路徑）并非一下子求出v0到v8的最短路徑字币，而是一步一步求出它們之間頂點的最短路徑则披，過過程中都是基于已經(jīng)求出的最短路徑的基礎(chǔ)上，求得更遠頂點的最短路徑洗出，最終得出源點與終點的最短路徑士复。
迪杰斯特拉(Dijkstra)算法代碼實現(xiàn)
核心代碼
/**
* Dijkstra算法，求有向網(wǎng)G的v0頂點到其余頂點v的最短路徑P[v]及帶權(quán)長度D[v]
* P[v]的值為前驅(qū)頂點下標翩活，D[v]表示v0到v的最短路徑長度和
*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc * P, ShortPathTable * D){
int v, w, k = 0, min;
int final[MAXVEX]; // final[w] = 1 表示求得頂點v0到vw的最短路徑
for (v = 0; v < G.numVertexes; v++) { // 初始化數(shù)據(jù)
final[v] = 0; // 全部頂點初始化為未知最短路徑狀態(tài)
(*D)[v] = G.arc[v0][v]; // 將與v0點有連線的頂點加上權(quán)值
(*P)[v] = 0; // 初始化路徑數(shù)組P為0
}
(*D)[v0] = 0; // v0到v0路徑為0
final[v0] = 1; // v0到v0不需要求路徑
for (v = 1; v < G.numVertexes; v++) { // 開始主循環(huán)阱洪，每次求得v0到某個v頂點的最短路徑
min = INFINITY;
for (w = 0; w < G.numVertexes; w++) { // 尋找離v0最近的頂點
if (!final[w] && (*D)[w] < min) {
k = w;
min = (*D)[w]; // w頂點離v0頂點更近
}
}
final[k] = 1; // 將目前找到的最近的頂點置為1
for (w = 0; w < G.numVertexes; w++) { // 修正當前最短路徑及距離
if (!final[w] && (min + G.arc[k][w] < (*D)[w])) { // 如果經(jīng)過v頂點的路徑比現(xiàn)在這條路徑的長度短的話
// 說明找到了根斷的路徑
(*D)[w] = min + G.arc[k][w]; // 修改當前路徑長度
(*P)[w] = k;
}
}
}
}
完整代碼和測試
#include <stdio.h>
#include <stdlib.h>
#define MAXEDGE 20
#define MAXVEX 10
#define INFINITY 65535
typedef struct {
int vex[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX]; // 用于存儲最短路徑下標的數(shù)組
typedef int ShortPathTable[MAXVEX]; // 用于存儲到各點最短路徑的權(quán)值和
/**
* 創(chuàng)建圖
*/
void CreateMGraph(MGraph * G){
int i, j;
G->numVertexes = 9; // 9個頂點
G->numEdges = 16; // 16條邊
for (i = 0; i < G->numVertexes; i++) // 初始化圖
G->vex[i] = i; //給頂點編號 這里是0 到 8
for (i = 0; i < G->numVertexes; i++) { // 初始化圖
for (j = 0; j < G->numVertexes; j++) {
if (i == j)
G->arc[i][j] = 0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1] = 1;
G->arc[0][2] = 5;
G->arc[1][2] = 3;
G->arc[1][3] = 7;
G->arc[1][4] = 5;
G->arc[2][4] = 1;
G->arc[2][5] = 7;
G->arc[3][4] = 2;
G->arc[3][6] = 3;
G->arc[4][5] = 3;
G->arc[4][6] = 6;
G->arc[4][7] = 9;
G->arc[5][7] = 5;
G->arc[6][7] = 2;
G->arc[6][8] = 7;
// 利用鄰接矩陣的對稱性
for (i = 0; i < G->numVertexes; i++)
for (j = 0; j < G->numVertexes; j++)
G->arc[j][i] = G->arc[i][j];
}
/**
* Dijkstra算法，求有向網(wǎng)G的v0頂點到其余頂點v的最短路徑P[v]及帶權(quán)長度D[v]
* P[v]的值為前驅(qū)頂點下標菠镇，D[v]表示v0到v的最短路徑長度和
*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc * P, ShortPathTable * D){
int v, w, k = 0, min;
int final[MAXVEX]; // final[w] = 1 表示求得頂點v0到vw的最短路徑
for (v = 0; v < G.numVertexes; v++) { // 初始化數(shù)據(jù)
final[v] = 0; // 全部頂點初始化為未知最短路徑狀態(tài)
(*D)[v] = G.arc[v0][v]; // 將與v0點有連線的頂點加上權(quán)值
(*P)[v] = 0; // 初始化路徑數(shù)組P為0
}
(*D)[v0] = 0; // v0到v0路徑為0
final[v0] = 1; // v0到v0不需要求路徑
for (v = 1; v < G.numVertexes; v++) { // 開始主循環(huán)冗荸，每次求得v0到某個v頂點的最短路徑
min = INFINITY;
for (w = 0; w < G.numVertexes; w++) { // 尋找離v0最近的頂點
if (!final[w] && (*D)[w] < min) {
k = w;
min = (*D)[w]; // w頂點離v0頂點更近
}
}
final[k] = 1; // 將目前找到的最近的頂點置為1
for (w = 0; w < G.numVertexes; w++) { // 修正當前最短路徑及距離
if (!final[w] && (min + G.arc[k][w] < (*D)[w])) { // 如果經(jīng)過v頂點的路徑比現(xiàn)在這條路徑的長度短的話
// 說明找到了根斷的路徑
(*D)[w] = min + G.arc[k][w]; // 修改當前路徑長度
(*P)[w] = k;
}
}
}
}
int main(int argc, const char * argv[]) {
int i, j, v0;
MGraph G;
Patharc P;
ShortPathTable D;
v0 = 0; // 求v0到其余各點的最短路徑
CreateMGraph(&G);
ShortestPath_Dijkstra(G, v0, &P, &D);
printf("源點到各個頂點的最短路徑如下：\n");
for (i = 1; i < G.numVertexes; i++) {
printf("v%d - v%d 最短路徑為：%2d 所經(jīng)過頂點: ",v0, i, D[i]);
j = i;
while (P[j] != 0) {
printf("v%d ", P[j]);
j = P[j];
}
printf("\n");
}
return 0;
}
測試結(jié)果
代碼解釋
-
用鄰接矩陣構(gòu)建圖。
- 用
Patharc數(shù)組存儲最短路徑下標,用ShortPathTable數(shù)組存儲各點最短路徑的權(quán)值和辟犀。 - 最終返回的數(shù)組
D和數(shù)組P俏竞，是可以得到v0到任意一個頂點的最短路徑和路徑長度的。 - 該算法的時間復雜度為
O(n^2)（因為有一個for循環(huán)嵌套）堂竟。
二、弗洛伊德(Floyd)算法
弗洛伊德(Floyd)算法是一個經(jīng)典的動態(tài)規(guī)劃算法玻佩。
弗洛伊德(Floyd)算法思路
- 從任意節(jié)點
i到任意節(jié)點j的最短路徑不外乎2種可能:1是直接從i到j出嘹，2是從i經(jīng)過若干個節(jié)點k到j。 - 所以咬崔，我們假設(shè)
Dis(i,j)為節(jié)點u到節(jié)點v的最短路徑的距離税稼，對于每一個節(jié)點k，我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立; - 如果成立垮斯，證明從
i到k再到j的路徑比i直接到j的路徑短郎仆，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來兜蠕，當我們遍歷完所有節(jié)點k扰肌，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。
弗洛伊德(Floyd)算法描述
- 從任意一條單邊路徑開始熊杨。所有兩點之間的距離是邊的權(quán)曙旭，如果兩點之間沒有邊相連盗舰，則權(quán)為無窮大.
- 對于每一對頂點
u和v，看看是否存在一個頂點w使得從u到w再到v比己知的路徑更短桂躏。如果是更新它钻趋。
弗洛伊德(Floyd)算法代碼實現(xiàn)
弗洛伊德(Floyd)算法核心代碼
/**
* Floyd算法，求網(wǎng)圖G中各個頂點v到其余各個頂點w的最短路徑P[v][w] 以及帶權(quán)長度D[v][w]
*/
void ShortestPaht_Floyd(MGraph G, Patharc *P, ShortPathTable *D){
int v,w,k;
for (v = 0; v < G.numVertexes; v++) { // 初始化D與P
for (w = 0; w < G.numVertexes; w++) {
(*D)[v][w] = G.arc[v][w]; //(*D)[v][w] 值即為對應(yīng)點之間的權(quán)值
(*P)[v][w] = w;
}
}
for (k = 0; k < G.numVertexes; k++) {
for (v = 0; v < G.numVertexes; v++) {
for (w = 0; w < G.numVertexes; w++) {
if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) { // 如果經(jīng)過下標為K頂點路徑比原兩點間路徑更短
(*D)[v][w] = (*D)[v][k] + (*D)[k][w]; // 將當前兩點間權(quán)值設(shè)置為更小的一個
(*P)[v][w] = (*P)[v][k]; // 路徑設(shè)置為經(jīng)過下標為k的頂點
}
}
}
}
}
完整代碼+測試代碼
#include <stdio.h>
#include <stdlib.h>
#define MAXEDGE 20
#define MAXVEX 10
#define INFINITY 65535
typedef struct {
int vex[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/**
* 創(chuàng)建圖
*/
void CreateMGraph(MGraph * G){
int i, j;
G->numVertexes = 9; // 9個頂點
G->numEdges = 16; // 16條邊
for (i = 0; i < G->numVertexes; i++) // 初始化圖
G->vex[i] = i; //給頂點編號 這里是0 到 8
for (i = 0; i < G->numVertexes; i++) { // 初始化圖
for (j = 0; j < G->numVertexes; j++) {
if (i == j)
G->arc[i][j] = 0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1] = 1;
G->arc[0][2] = 5;
G->arc[1][2] = 3;
G->arc[1][3] = 7;
G->arc[1][4] = 5;
G->arc[2][4] = 1;
G->arc[2][5] = 7;
G->arc[3][4] = 2;
G->arc[3][6] = 3;
G->arc[4][5] = 3;
G->arc[4][6] = 6;
G->arc[4][7] = 9;
G->arc[5][7] = 5;
G->arc[6][7] = 2;
G->arc[6][8] = 7;
// 利用鄰接矩陣的對稱性
for (i = 0; i < G->numVertexes; i++)
for (j = 0; j < G->numVertexes; j++)
G->arc[j][i] = G->arc[i][j];
}
/**
* Floyd算法剂习，求網(wǎng)圖G中各個頂點v到其余各個頂點w的最短路徑P[v][w] 以及帶權(quán)長度D[v][w]
*/
void ShortestPaht_Floyd(MGraph G, Patharc *P, ShortPathTable *D){
int v,w,k;
for (v = 0; v < G.numVertexes; v++) { // 初始化D與P
for (w = 0; w < G.numVertexes; w++) {
(*D)[v][w] = G.arc[v][w]; //(*D)[v][w] 值即為對應(yīng)點之間的權(quán)值
(*P)[v][w] = w;
}
}
for (k = 0; k < G.numVertexes; k++) {
for (v = 0; v < G.numVertexes; v++) {
for (w = 0; w < G.numVertexes; w++) {
if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) { // 如果經(jīng)過下標為K頂點路徑比原兩點間路徑更短
(*D)[v][w] = (*D)[v][k] + (*D)[k][w]; // 將當前兩點間權(quán)值設(shè)置為更小的一個
(*P)[v][w] = (*P)[v][k]; // 路徑設(shè)置為經(jīng)過下標為k的頂點
}
}
}
}
}
int main(int argc, const char * argv[]) {
int v, w,k;
MGraph G;
Patharc P;
ShortPathTable D;
CreateMGraph(&G);
ShortestPaht_Floyd(G, &P, &D);
printf("各頂點間最短路徑如下：\n");
for (v = 0; v < G.numVertexes; v++) {
for (w = v+1; w < G.numVertexes; w++) {
printf("v%d - v%d weight：%d", v,w,D[v][w]);
k = P[v][w]; // 獲得第一個路徑頂點下標
printf(" path: %d", v); // 打印源點
while (k != w) { // 如果路徑頂點下標不是終點
printf(" —> %d",k); // 打印路徑頂點
k = P[k][w]; // 獲得下一個路徑頂點下標
}
printf(" -> %d\n", w);
}
printf("\n");
}
return 0;
}
弗洛伊德(Floyd)算法
代碼解釋
- 弗洛伊德(Floyd)算法的代碼非常簡潔蛮位，就是一個二重初始化加上一個三重循環(huán)權(quán)值修正，就完成了所有頂點到所有頂點的最短路徑計算鳞绕。
- 弗洛伊德(Floyd)算法的時間復雜度為
O(n^3)失仁。
