最短路径顾名思义就是两个点之间所需花费最短的那个路径。在算法中计算最短路径有两个比较著名的算法：Dijkstra算法和Floyd算法
1、Dijkstra算法
Dijkstra算法设计3个数组来保存相应的数据并实施更新，从而达到找到最短路径的目的：
Dijkstra算法@2x.png
代码实现：
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status;
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/*用于存储最短路径下标的数组*/
typedef int Patharc[MAXVEX];
/*用于存储到各点最短路径权值的和*/
typedef int ShortPathTable[MAXVEX];
/*10.1 创建邻近矩阵*/
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)
{
G->vexs[i]=i;
}
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] = INFINITYC;
}
}
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;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/*10.2 求得网图中2点间最短路径
Dijkstra 算法
G: 网图;
v0: V0开始的顶点;
p[v]: 前驱顶点下标;
D[v]: 表示从V0到V的最短路径长度和;
*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v,w,k,min;
k = 0;
/*final[w] = 1 表示求得顶点V0~Vw的最短路径*/
int final[MAXVEX];
/*1.初始化数据*/
for(v=0; v<G.numVertexes; v++)
{
//全部顶点初始化为未知最短路径状态0
final[v] = 0;
//将与V0 点有连线的顶点最短路径值;
(*D)[v] = G.arc[v0][v];
//初始化路径数组p = 0;
(*P)[v] = 0;
}
//V0到V0的路径为0
(*D)[v0] = 0;
//V0到V0 是没有路径的.
final[v0] = 1;
//v0到V0是没有路径的
(*P)[v0] = -1;
//2. 开始主循环,每次求得V0到某个顶点的最短路径
for(v=1; v<G.numVertexes; v++)
{
//当前所知距离V0顶点最近的距离
min=INFINITYC;
/*3.寻找离V0最近的顶点*/
for(w=0; w<G.numVertexes; w++)
{
if(!final[w] && (*D)[w]<min)
{
k=w;
//w顶点距离V0顶点更近
min = (*D)[w];
}
}
//将目前找到最近的顶点置为1;
final[k] = 1;
/*4.把刚刚找到v0到v1最短路径的基础上,对于v1 与 其他顶点的边进行计算,得到v0与它们的当前最短距离;*/
for(w=0; w<G.numVertexes; w++)
{
//如果经过v顶点的路径比现在这条路径长度短,则更新
if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
{
//找到更短路径, 则修改D[W],P[W]
//修改当前路径的长度
(*D)[w] = min + G.arc[k][w];
(*P)[w]=k;
}
}
}
}
2、Floyd算法
Floyd算法是通过中间点的思想来找到最短路径。
D0[v][w]=min{ D-1 [v][w],D-1[v][0]+D-1 [0][w]}
代码实现：
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* 11.1 构成邻近矩阵 */
void CreateMGraph(MGraph *G)
{
int i, j;
/* printf("请输入边数和顶点数:"); */
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
G->vexs[i]=i;
}
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] = INFINITYC;
}
}
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;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* 11. 2
Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。
Patharc 和 ShortPathTable 都是二维数组;
*/
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
int v,w,k;
/* 1. 初始化D与P 矩阵*/
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
/* D[v][w]值即为对应点间的权值 */
(*D)[v][w]=G.arc[v][w];
/* 初始化P P[v][w] = w*/
(*P)[v][w]=w;
}
}
//2.K表示经过的中转顶点
for(k=0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
/*如果经过下标为k顶点路径比原两点间路径更短 */
if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
{
/* 将当前两点间权值设为更小的一个 */
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
/* 路径设置为经过下标为k的顶点 */
(*P)[v][w]=(*P)[v][k];
}
}
}
}
}
网友评论