数据结构——迪杰斯特拉算法求最短路径

问题描述

将图以邻接矩阵或邻接表存储，实现Dijkstra算法。

算法设计

迪杰斯特拉算法：

1.假设用带权的邻接矩阵arc，来表示带权有向图，arc[i][j]，表示弧<vi,vj>上的权值。若<vi,vj>不存在，则置arc[i][j]为无穷。
S为已找到从v出发的最短路径的终点的集合，它的初始状态为空集。那么，从v出发到图上其余各顶点可能达到的最短路径长度的初值为:
D[j]=arcs[LocateVex(G,v)][i] vi∈V

2.选择vj，使得 D[j]=Min{D[i]|vi∈V-S}
vj就是当前求得的一条从v出发的最短路径的终点。令S=S∪{j}

3.修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果
D[j]+arcs[j][k]<D[k] 则修改D[k]为D[k]=D[j]+arcs[j][k]

4.重复操作2，3共n-1次。
由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。

算法实现

代码

#include "stdio.h"
#include "stdlib.h"
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
#define InfoType char   //存储弧或者边额外信息的指针变量类型
#define VertexType char  //图中顶点的数据类型
int P[MAX_VERTEX_NUM]; //用于存储最短路径下标的数组
int D[MAX_VERTEX_NUM];  //用于存储到各点最短路径的权值typedef struct ArcCell{int adj;  //权值InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];  //顶点的向量AdjMatrix arcs;int vexnum;  //顶点数int arcnum;  //弧数
}MGraph;int LocateVex(MGraph *G,VertexType v){int i;for(i=0;i<G->arcnum;i++){if(G->vexs[i]==v)return i;}if(i>=G->arcnum)return -1;elsereturn -1;
}void CreateGraph(MGraph *G){printf("输入顶点数和弧数：\n");scanf("%d%d",&G->vexnum,&G->arcnum);printf("输入顶点的元素：\n");for(int i=0;i<G->vexnum;i++){getchar();scanf("%c",&G->vexs[i]);}for(int i=0;i<G->vexnum;i++)for(int j=0;j<G->vexnum;j++){G->arcs[i][j].adj=INFINITY;G->arcs[i][j].info=NULL;}printf("输入各个弧及权值：\n");for(int i=0;i<G->arcnum;i++){char a1,a2,a3;int w,n1,n2;getchar();scanf("%c%c%c%d",&a1,&a2,&a3,&w);n1=LocateVex(G,a1);n2=LocateVex(G,a3);if(n1==-1 || n2==-1){printf("no this vertex.\n");return;}G->arcs[n1][n2].adj=w;}
}//输出邻接矩阵
void PrintGraph(MGraph G){printf("邻接矩阵：\n");for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){printf("%d ",G.arcs[i][j].adj);}printf("\n");}
}void Dijkstra(MGraph G,int v0){int v,w,k,min;int final[MAX_VERTEX_NUM];for(v=0;v<G.vexnum;v++){final[v]=0;D[v]=G.arcs[v0][v].adj;P[v]=0;}D[v0]=0;final[v0]=1;for(v=1;v<G.vexnum;v++){min=INFINITY;for(w=0;w<G.vexnum;w++){if(!final[w]&&D[w]<min){k=w;min=D[w];}}final[k]=1;for(w=0;w<G.vexnum;w++){if(!final[w] && (min+G.arcs[k][w].adj<D[w])&&G.arcs[k][w].adj!=INFINITY){D[w]=min+G.arcs[k][w].adj;P[w]=k;}}}
}void Print(MGraph G,int v){printf("\n");for(int i=0;i<G.vexnum;i++){if(i!=v && D[i]!=INT_MAX){printf("%c到%c的最短距离为：%d\n",G.vexs[v],G.vexs[i],D[i]);}else if(D[i]==INT_MAX){printf("%c与%c之间无路径！\n",G.vexs[v],G.vexs[i]); } }
}int main(){MGraph G;CreateGraph(&G);PrintGraph(G);Dijkstra(G,0);Print(G,0);system("pause");return 0;}

结果