数据结构--6.0最短路径

目录

一、迪杰斯特拉算法（Dijkstra）

二、弗洛伊德算法（Floyd）

---

 

在网图和非网图中，最短路径的含义是不同的。

——网图是两顶点经过的边上的权值之和最少的路径。                                                                    

——非网图是两顶点之间经过的边数最少的路径。

我们把路径起始的第一个顶点称为源头，最后一个顶点称为终点。

关于最短路径的算法：

1、迪杰斯特拉算法（Dijkstra）

2、弗洛伊德算法（Floyd）

一、迪杰斯特拉算法（Dijkstra）

#include <stdio.h>
#include <stdlib.h>#define MAXVEX 9
#define INFINITY 65536typedef int Patharc[MAXVEX];				//用于存储最短路径下标的数组 
typedef int ShortPathTable[MAXVEX];			//用于存储到各点最短路径的权值 void ShortestPath_Dijkstra(MGraph G , int V0,Patharc *p,ShortPathTable *D)
{int v,w,k,min;int final[MAXVEX];						//final[w]=1 表示已经求得顶点v0到vw的最短路径 //初始化数据 for(v=0;v<G.numVertexes; v++){final[v] = 0;						//全部顶点初始化为未找到最短路径 (*D)[v] = G.arc{V0}[v];				//将与v0点有连接线的顶点加上权值 (*p)[v] = 0;						//初始化路径数组p为0 }(*D)[V0] = 0;					//v0至v0的路径为0 final[v0] = 1;					//v0至v0不需要求路径 //开始主循环，每次求得v0到某个v顶点的最短路径 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 //修正当前最短路径及距离 for(w=0; w<G.numVextexes;w++){//如果经过v顶点的路径比现在这条路径的长度短的话，更新！ if( !final[w]&&(min+G.arc[k][w] < (*D)[w])){(*D)[w] = min + G.arc[k][w];		//修改当前路径长度 (*p)[w] = k;						//存放前驱顶点 }} }
}

二、弗洛伊德算法（Floyd）

        弗洛伊德算法非常简洁优雅。

 

#include <stdio.h>
#include <stdlib.h>#define MAXVEX 9
#define INFINITY 65536typedef 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];}}}}
}