生活封鎖了我們，只要我們的心不死，生活便永遠(yuǎn)不是一汪死水，而我們，依然會(huì)綻放最美的姿態(tài)。
什么是迪杰斯特拉算法??
算法來(lái)歷
戴克斯特拉算法（英語(yǔ)：Dijkstra’s algorithm），又稱迪杰斯特拉算法、Dijkstra算法，是由荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾·戴克斯特拉在1956年發(fā)現(xiàn)的算法，并于3年后在期刊上發(fā)表。戴克斯特拉算法使用類似廣度優(yōu)先搜索的方法解決賦權(quán)圖的單源最短路徑問(wèn)題。
該算法存在很多變體：戴克斯特拉的原始版本僅適用于找到兩個(gè)頂點(diǎn)之間的最短路徑，后來(lái)更常見(jiàn)的變體固定了一個(gè)頂點(diǎn)作為源結(jié)點(diǎn)然后找到該頂點(diǎn)到圖中所有其它結(jié)點(diǎn)的最短路徑，產(chǎn)生一個(gè)最短路徑樹(shù)。
算法的用途
該算法解決了圖 上帶權(quán)的單源最短路徑問(wèn)題。具體來(lái)說(shuō)，戴克斯特拉算法設(shè)置了一頂點(diǎn)集合S，在集合S中所有的頂點(diǎn)與源點(diǎn)s之間的最終最短路徑權(quán)值均已確定。該算法常用于路由算法或者作為其他圖算法的一個(gè)子模塊。舉例來(lái)說(shuō)，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示城市間開(kāi)車行經(jīng)的距離，該算法可以用來(lái)找到兩個(gè)城市之間的最短路徑。
迪杰斯特拉算法的理論??
首先舉出圖例1，在圖中選擇下標(biāo)為0的V0點(diǎn)開(kāi)始遍歷。
不難看出，從v0開(kāi)始選擇最短路徑，即V0->V1，再進(jìn)行選擇遍歷，即V0->V1->V2,如圖例2所示。
如此反復(fù)，就可以得到源點(diǎn)V0至終點(diǎn)V8的最短權(quán)值路徑。如圖例3所示。
迪杰斯特拉算法實(shí)現(xiàn)??
首先，我們需要知道，迪杰斯特拉算法是基于鄰接矩陣實(shí)現(xiàn)的，如過(guò)對(duì)于鄰接矩陣還有些不熟悉的同學(xué)可以復(fù)習(xí)一下點(diǎn)我復(fù)習(xí)鄰接矩陣
之前的圖結(jié)構(gòu)，轉(zhuǎn)化成鄰接矩陣如圖例4所示。
宏定義
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 65535
#define MAXVEX 9
typedef int Patharc[MAXVEX]; //用于存儲(chǔ)最短路徑下標(biāo)的數(shù)組
typedef int ShortPathTable[MAXVEX];//用于存儲(chǔ)最短路徑的權(quán)值和
typedef char VertexType; //頂點(diǎn)類型
typedef int EdgeType; //邊上的權(quán)值
前提函數(shù)實(shí)現(xiàn)
typedef struct
{
VertexType vexs[MAXVEX];//頂點(diǎn)表
EdgeType arc[MAXVEX][MAXVEX];//鄰接矩陣
int numVertexes, numEdges;//頂點(diǎn)數(shù)以及邊數(shù)
}MGraph;
void CreateMGraph(MGraph* G)
{
int k, w;
char i, j;
printf("輸入頂點(diǎn)數(shù)和邊數(shù)：\n");
scanf("%d%d", &G->numVertexes, &G->numEdges);
printf("請(qǐng)輸入頂點(diǎn)信息：");
getchar();
for (i = 0; i < G->numVertexes; i++)//分別輸入頂點(diǎn)信息
{
scanf("%c", &G->vexs[i]);
getchar();
}
for (i = 0; i < G->numVertexes; i++)
for (j = 0; j < G->numVertexes; j++)
G->arc[i][j] = INFINITY; //初始化所有點(diǎn)之間權(quán)無(wú)窮大
for (k = 0; k < G->numEdges; k++)
{
printf("輸入邊(vi,vj)上的下標(biāo)i，下標(biāo)j和權(quán)w:\n");
scanf("%d%d%d", &i, &j, &w);
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j];//無(wú)向圖，矩陣對(duì)稱
}
}
迪杰斯特拉算法
void ShortestPath_Dijkstra(MGraph G, int V0, Patharc* P, ShortPathTable* D)
{
int v, w, k, min;
int final[MAXVEX]; //final[w]=1表示求得頂點(diǎn)V0至Vw的最短路徑
for (v = 0; v < G.numVertexes; v++)
{
final[v] = 0; //全部頂點(diǎn)初始化為未知最短路徑狀態(tài)
(*D)[v] = G.arc[V0][v]; //將與V0點(diǎn)有連線的頂點(diǎn)加上權(quán)值
(*P)[v] = 0; //初始化路徑數(shù)組P為0
}
(*D)[V0] = 0; //v0至v0的路徑為0
final[V0] = 1; //v0至v0不需要求路徑
//開(kāi)始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑
for (v = 1; v < G.numVertexes; v++)
{
min = INFINITY;
for (w = 0; w < G.numVertexes; w++)
{
if (!final[w] && (*D)[w] < min)
{
k = w;
min = (*D)[w]; //w頂點(diǎn)距離v0更近
}
}
final[k] = 1; //表示k下標(biāo)的頂點(diǎn)已經(jīng)在路徑中
for (w = 0; w < G.numVertexes; w++)//檢查一遍
{
if (!final[w] && (min+G.arc[k][w]<(*D)[w]))
{
(*D)[w] = min + G.arc[k][w];
(*P)[w] = k;
}
}
}
}
主函數(shù)實(shí)現(xiàn)
int main()
{
MGraph G;
CreateMGraph(&G);
Patharc P;
ShortPathTable D;
ShortestPath_Dijkstra(G,0,&P,&D);
}
調(diào)試結(jié)果
1) D數(shù)組中每個(gè)下標(biāo)的的數(shù)據(jù)對(duì)應(yīng)到達(dá)此下標(biāo)頂點(diǎn)的最短權(quán)值。
2) final數(shù)組表示數(shù)組中的各點(diǎn)是否進(jìn)入最短路徑。
3）P數(shù)組表示數(shù)組中的各點(diǎn)的前一個(gè)頂點(diǎn)
代碼解析
定義一個(gè)用于存儲(chǔ)最短路徑下標(biāo)的數(shù)組
typedef int Patharc[MAXVEX];
Patharc P;
定義一個(gè)用于存儲(chǔ)最短權(quán)值和的數(shù)組
typedef int ShortPathTable[MAXVEX];
ShortPathTable D;
定義一個(gè)判斷一點(diǎn)是否進(jìn)入最短路徑的數(shù)組，1表示已進(jìn)入，0表示未進(jìn)入。
int final[MAXVEX];
對(duì)各項(xiàng)數(shù)據(jù)進(jìn)行初始化，以便進(jìn)行遍歷。
for (v = 0; v < G.numVertexes; v++)
{
final[v] = 0; //全部頂點(diǎn)初始化為未知最短路徑狀態(tài)
(*D)[v] = G.arc[V0][v]; //將與V0點(diǎn)有連線的頂點(diǎn)加上權(quán)值
(*P)[v] = 0; //初始化路徑數(shù)組P為0
}
(*D)[V0] = 0; //v0至v0的路徑為0
final[V0] = 1; //v0至v0不需要求路徑
進(jìn)行第一遍遍歷，注意這里的（*D）[]是之前初始化的第一行數(shù)組數(shù)據(jù)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-766570.html
min = INFINITY;
for (w = 0; w < G.numVertexes; w++)
{
if (!final[w] && (*D)[w] < min)
{
k = w;
min = (*D)[w]; //w頂點(diǎn)距離v0更近
}
}
final[k] = 1; //表示k下標(biāo)的頂點(diǎn)已經(jīng)在路徑中
這可以進(jìn)行第一遍遍歷，但是再往下走就不可以了，所以有了下列代碼補(bǔ)全。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-766570.html
for (w = 0; w < G.numVertexes; w++)//檢查一遍
{
if (!final[w] && (min+G.arc[k][w]<(*D)[w]))
{
(*D)[w] = min + G.arc[k][w];
(*P)[w] = k;
}
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--迪杰斯特拉（Dijkstra）算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
