数据结构
创建图的邻接矩阵
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];
}
}
}
Dijkstra(迪科斯彻) 算法求图的最短路径
Dijkstra(迪科斯彻) 算法核心思想
-
Dijkstra(迪科斯彻)算法是基于贪心算法思想实现的。即始终保持当前迭代解为当前最优解。也可以看作一种动态规划的思想,始终获取当前拥有的条件下的最优解，当迭代中于加入了新的条件使得产生了新的最优解则更新子此问题的最优解。当迭代到最后一轮时得到的就是全局最优解。由于每一轮迭代都会参考之前的最优解，减少重复工作,数据有效进行传递，降低了整体工作的复杂性。在最短路径的问题中，局部最优解即当前的最短路径或者说是在当前的已知条件下起点到其余各点的最短距离。
-
Dijkstra 主要由三个一维数组实现
- final 表示V0 到某个顶点Vm是否已经求得了最短路径的标记,如有有则final[m] = 1;
- Patharc P 表示当前结点的前驱结点的下标 比如从V0走到V1 则Patharc[1] = 0;
- ShortPathTable D 存储V0 到某个顶点的路径 for 循环打印的结果就为V0到Vm 的最短路径
/*用于存储最短路径下标的数组*/
typedef int Patharc[MAXVEX];
/*用于存储到各点最短路径权值的和*/
typedef int ShortPathTable[MAXVEX];
void ShortestPath_Dijkstra(MGraph G,int v0, Patharc *P ,ShortPathTable *D){
// 初始化
int final[MAXVEX] = {0};
int i,w,k = 0,min;
for ( i= 0; i<G.numVertexes; i++) {
(*D)[i] = G.arc[v0][i];
(*P)[i] = 0;
}
// 当前D 为 0 1 5 # # # # # #
// final、P 为 0 0 0 0 0 0 0 0 0
//V0到V0的路径为V0本身没有路径
(*D)[v0] = 0;
//V0到V0 是没有路径的.默认已经求得最短路径 不在计算
final[v0] = 1;
//v0到V0是没有路径的前驱为-1,标示无前驱
(*P)[v0] = -1;
// 要找的路径的数 总共8个顶点 找7次
for(i = 1; i<G.numVertexes ; i++){
// 每一次查找下一个路径的时候 min 初始化为INFINITYC
min = INFINITYC;
for(w=0;w<G.numVertexes;w++){
// 找到 当前D中的最小权值的位置 下标用k记录
if (final[w]==0 && (*D)[w]<min) {
k = w;
min = (*D)[w];
}
}
// 将找到最小权值的顶点加入 final数组 表示当前顶点已经走过了
// 第一次执行 D 中最小的为 1 k也为1
final[k]=1;
// 把刚刚找到v0到v1最短路径的基础上,对于v1 与 其他顶点的边进行计算,得到v0与它们的当前最短距离
for(w=0; w<G.numVertexes; w++)
{
// 如果经过v顶点的路径比现在这条路径长度短,则更新 当前的(*D)[w]第一次为5 表示V0 ->V2 直接前往的权值
// 此时V0->V1 的权值为1 V1 ->v2 的权值为3 那么V0->v1->v2的权值sum是4要小于之前存储的5
// 此时更新D[2]的数据为4 表示V0->v2的最小路径权值为4
// 此循环表示遍历当前所有顶点查找为被访问的结点 是否有比直接连接顶点还小的路径,如果有加入数组,更新数据
if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
{
//找到更短路径, 则修改D[W],P[W]
//修改当前路径的长度
(*D)[w] = min + G.arc[k][w];
(*P)[w]=k;
}
}
}
}
int main(void)
{
printf("Dean最短路径-Dijkstra算法\n");
int i,j,v0;
MGraph G;
Patharc P;
ShortPathTable D;
v0=0;
CreateMGraph(&G);
ShortestPath_Dijkstra(G, v0, &P, &D);
printf("最短路径路线:\n");
for(i=1;i<G.numVertexes;++i)
{
printf("v%d -> v%d : ",v0,i);
j=i;
while(P[j]!=-1)
{
printf("%d ",P[j]);
j=P[j];
}
printf("\n");
}
printf("\n最短路径权值和\n");
for(i=1;i<G.numVertexes;++i)
printf("v%d -> v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);
printf("\n");
return 0;
}
Dijkstra 算法的缺点
Dijkstra 算法我们只能只能得到V0到其他顶点到最短路径,Floyd则可以获取到所有到路径以及最短路径到权值sum,Floyd 因此Floyd 利用到二维来进行数据存储
Floyd(弗洛伊德)算法求图的最短路径
Floyd算法核心思想
Floyd算法是一个经典的动态规划算法,又称为插点法.是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,算法目标是寻找从点i到点j的最短路径。 Floyd 算法中主要查找是否有一个中间变量 k 使得当前路径有更小的路径
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
int v,w,k;
/* 初始化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]就是v顶点到w顶点的中转节点，初始化默认可以直接到达无中间结点，递归后发现有中转顶点k，则更新
(*P)[v][w]=w;
}
}
//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];
}
}
}
}
}
main 中打印代码
int main(void)
{
printf("Hello,最短路径弗洛伊德Floyd算法");
int v,w,k;
MGraph G;
Patharc P;
ShortPathTable D; /* 求某点到其余各点的最短路径 */
CreateMGraph(&G);
ShortestPath_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");
}
//打印最终变换后的最短路径D数组
printf("最短路径D数组\n");
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
printf("%d\t",D[v][w]);
}
printf("\n");
}
//打印最终变换后的最短路径P数组
printf("最短路径P数组\n");
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
printf("%d\t",P[v][w]);
}
printf("\n");
}
return 0;
}
以V0 到 V2 为例
最短路径权值和为D[0][2] 也就是4 经过到路径 就是从V0 开始 P[0][2]为1,不等于2
所以1为中转顶点,路径变为V0->V1 此时 P[1][2] 为2 等于2
没有中转顶点,退出查找中转顶点,路径最终为V0->V1->V2
