目錄
一、迪杰斯特拉算法（Dijkstra）
二、弗洛伊德算法（Floyd）
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-691228.html
在網(wǎng)圖和非網(wǎng)圖中，最短路徑的含義是不同的。
——網(wǎng)圖是兩頂點(diǎn)經(jīng)過(guò)的邊上的權(quán)值之和最少的路徑。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
——非網(wǎng)圖是兩頂點(diǎn)之間經(jīng)過(guò)的邊數(shù)最少的路徑。
我們把路徑起始的第一個(gè)頂點(diǎn)稱為源頭，最后一個(gè)頂點(diǎn)稱為終點(diǎn)。
關(guān)于最短路徑的算法：
1、迪杰斯特拉算法（Dijkstra）
2、弗洛伊德算法（Floyd）
一、迪杰斯特拉算法（Dijkstra）
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 9
#define INFINITY 65536
typedef int Patharc[MAXVEX]; //用于存儲(chǔ)最短路徑下標(biāo)的數(shù)組
typedef int ShortPathTable[MAXVEX]; //用于存儲(chǔ)到各點(diǎn)最短路徑的權(quán)值
void ShortestPath_Dijkstra(MGraph G , int V0,Patharc *p,ShortPathTable *D)
{
int v,w,k,min;
int final[MAXVEX]; //final[w]=1 表示已經(jīng)求得頂點(diǎn)v0到vw的最短路徑
//初始化數(shù)據(jù)
for(v=0;v<G.numVertexes; v++)
{
final[v] = 0; //全部頂點(diǎn)初始化為未找到最短路徑
(*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; v++)
{
if(!final[w]&&(*D)[w]<min)
{
k = w;
min = (*D)[w];
}
}
final[k] = 1;//將目前找到的最短路徑置1
//修正當(dāng)前最短路徑及距離
for(w=0; w<G.numVextexes;w++)
{
//如果經(jīng)過(guò)v頂點(diǎn)的路徑比現(xiàn)在這條路徑的長(zhǎng)度短的話，更新！
if( !final[w]&&(min+G.arc[k][w] < (*D)[w]))
{
(*D)[w] = min + G.arc[k][w]; //修改當(dāng)前路徑長(zhǎng)度
(*p)[w] = k; //存放前驅(qū)頂點(diǎn)
}
}
}
}
二、弗洛伊德算法（Floyd）
? ? ? ? 弗洛伊德算法非常簡(jiǎn)潔優(yōu)雅。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-691228.html
?
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 9
#define INFINITY 65536
typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
void ShortestPath_Floyd(MGraph.G,Pathmatirx *p,ShortPathTable *D)
{
int v,w,k;
//初始化 D 和 p
for(v=0;v<G.numVertexes;w++)
{
for(w=0;w<G.numVertexes;w++)
{
(*D)[v][w] = G.matirx[v][m];
(*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]))
{
(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
(*p)[v][w] = (*p)[v][k];
}
}
}
}
} 到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--6.0最短路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
