问题描述
将图以邻接矩阵或邻接表存储，实现算法 。
算法设计
迪杰斯特拉算法：
1.假设用带权的邻接矩阵arc，来表示带权有向图，arc[i][j] ， 表示弧上的权值 。若不存在，则置arc[i][j]为无穷 。
S为已找到从v出发的最短路径的终点的集合 ， 它的初始状态为空集 。那么，从v出发到图上其余各顶点可能达到的最短路径长度的初值为:
D[j]=arcs[(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]
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;iarcnum;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;ivexnum;i++){getchar();scanf("%c",&G->vexs[i]);}for(int i=0;ivexnum;i++)for(int j=0;jvexnum;j++){G->arcs[i][j].adj=INFINITY;G->arcs[i][j].info=NULL;}printf("输入各个弧及权值：\n");for(int i=0;iarcnum;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
【数据结构——迪杰斯特拉算法求最短路径】结果