一、迪杰斯特拉算法(Dijkstra算法)
（1）算法
从某一顶点到其余各项顶点的最短路径。
引进三个辅助数组dist[]、path[]和set[]。
dist[vi]表示当前已找到的从v0到vi的最短路径长度。
path[vi]中保存从v0到vi最短路径上vi的前一个顶点。
set[]为标记数组。
/*邻接矩阵的结构定义*/
#define maxSize 100
typedef struct{
int edges[maxSize][maxSize]; //邻接矩阵定义
int n, e; //分别为顶点数和边数
}MGraph;
/*最短路径，迪杰斯特拉算法(Dijkstra算法)，从某一顶点到其余各项顶点的最短路径*/
void Dijkstra(MGraph g, int v0, int dist[], int path[]){
int set[maxSize]; //标记数组
int i, j, min, v;
/*对各数组进行初始化*/
for(i=0;i<g.n;i++){
dist[i]=g.edges[v0][i];
set[i]=0;
if(g.edges[v0][i]<INF)
path[i]=v0;
else
path[i]=-1;
}
set[v0]=1;
path[v0]=-1;
/*初始化结束*/
/*关键操作开始*/
for(i=0;i<g.n-1;i++){
min=INF;
/*这个循环每次从剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的*/
for(j=0;j<g.n;j++){
if(set[j]==0&&dist[j]<min){
v=j;
min=dist[j];
}
}
set[v]=1; //将选出的顶点并入最短路径中
/*这个循环以刚并入的顶点作为中间点，对所有通往剩余顶点的路径进行检测*/
for(j=0;j<g.n;j++){
/*这个if语句判断顶点v的加入是否会出现通往顶点j的更短的路径，如果出现，则改变原来路径及其长度，否则什么都不做*/
if(set[j]==0&&dist[v]+g.edges[v][j]<dist[j]){
dist[j]=dist[v]+g.edges[v][j];
path[j]=v;
}
}
}
}
/*函数结束时，dist[]数组中存放了v点到其余顶点的最短路径长度，path[]中存放v点到其余各顶点的最短路径*/
（2）时间复杂度
迪杰斯特拉算法的时间复杂度为O(n2)。
（3）path[]数组打印最短路径经过的所有顶点
path[]数组中其实保存了一棵树，这是一棵用双亲存储结构存储的树，通过这棵树可以打印出从源点到任何一个顶点最短路径上所经过的所有顶点。
树的双亲表示法只能输出由叶子结点到根结点的路径，而不能逆向输出，因此需要借助一个栈来实现逆向输出。
void printfPath(int path[], int a){
int stack[maxSize];
int top=-1;
/*此循环以由叶子结点到根结点的顺序将其入栈*/
while(path[a]!=-1){
stack[++top]=path[a];
a=path[a];
}
stack[++top]=a;
while(top!=-1){
cout<<stack[top--]<<" "; //出栈并打印出栈元素，实现了顶点的逆序打印
cout<<endl;
}
}
二、弗洛伊德算法(Floyd算法)
（1）算法
求图中任意一对顶点间的最短路径。
void Floyd(MGraph g, int path[][maxSize]){
int i, j, v;
int A[maxSize][maxSize];
/*下面这个双循环对数组A[][]和path[][]进行了初始化*/
for(i=0;i<g->n;i++)
for(j=0;j<g->n;j++){
A[i][j]=g->edges[i][j];
path[i][j]=-1;
}
/*以下三层循环完成了以k为中间点，对所有顶点对(i,j)进行检测和修改*/
for(v=0;v<g->n;v++)
for(i=0;i<g->n;i++)
for(j=0;j<g->n;j++){
if(A[i][j]>A[i][v]+A[v][j]){
A[i][j]=A[i][v]+A[v][j];
path[i][j]=v;
}
}
}
（2）时间复杂度
佛洛依德算法的时间复杂度为O(n^3)。
（3）输出u、v两个顶点之间的最短路径的顶点序列
/*伪代码*/
void printPath(int u, int v, int path[][maxSize]){
if(path[u][v]==-1)
直接输出；
else{
int mid=path[u][v];
printPath(u,min,path);
printPath(min,v,path);
}
}
三、广度优先搜索(BFS)算法（无权图）
（1）算法
/*图的邻接矩阵存储结构定义*/
#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
int vernum, arcnum;
}MGraph;
//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(MGraph G, int u){
//d[i]表示从u到i结点的最短路径
for(int i=0;i<G.vernum;i++){
d[i]=∞; //初始化路径长度
path[i]=-1; //最短路径从哪个顶点过来
visited[i]=false; //标记数组
}
d[u]=0;
visited[u]=true;
EnQueue(Q,u);
while(!IsEmpty(Q)){ //BFS算法主过程
DeQueue(Q,u); //队头元素u出队
for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
if(!visited[w]){ //w为u的尚未访问过的邻接顶点
d[w]=d[u]+1; //路径长度加1
path[w]=u; //最短路径应从u到w
visited[w]=true; //设已访问标记
EnQueue(Q,w); //顶点w入队
}
}
}
}
|