一、基础知识
二、代码要求
邻接矩阵、邻接表中任选一种作为图的存储结构，采用迪杰斯特拉（Dijkstra）算法，实现指定的单源点到图中其余各顶点的最短路径（2学时）
三、算法思路分析
四、算法反思
五、代码实现
#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
#define INF 32767 //INF表示无穷
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
VertexType vexs[MaxVertexNum];//顶点表
EdgeType edges[MaxVertexNum][MaxVertexNum];//边表，邻接矩阵
int n,e;//顶点数和边数
}MGraph;//以邻接矩阵存储图类型
struct node
{
int adjvex;
int lowcost; //存储该边上的权
}closedge[MaxVertexNum];//一维辅助数组，记录从U到U-V具有最小权值的边 （U是生成树顶点集合）
int visited[MaxVertexNum];
int CreateMGraph(MGraph *G)//建立图的邻接矩阵
{
int i, j, k, weight;
printf("请输入顶点数和边数（输入格式为：顶点数，边数）：\n");
scanf("%d,%d",&(G->n),&(G->e));//输入顶点数和边数 /*这G->n不加括号括起来有无影响？*/
printf("请输入顶点信息（输入格式为：<回车>顶点号）：\n");
for(i=0; i<G->n; i++)
{
scanf("\n%c",&(G->vexs[i]));//输入顶点信息，顶点集
}
for(i=0; i<G->n; i++)
{
for(j=0; j<G->n; j++)
{
G->edges[i][j]=INF;//初始化邻接矩阵
}
}
printf("请输入每条边对应的两个顶点的序号和对应的权值（输入格式为：i,j,weight）：\n");
for(k=0; k<G->e; k++)
{
scanf("%d,%d,%d",&i,&j,&weight);
G->edges[i][j]=weight;//若此处加入G->deges[j][i]=1,则为无向图的邻接矩阵存储建立
// G->edges[j][i]=weight;
}
/*用来显示邻接矩阵，检测创建是否正确
for(i=0; i<G->n; i++)
{
for(j=0; j<G->n; j++)
{
printf("(%d)",G->edges[i][j]);
}
printf("\n");
}
*/
}
void dispath(int dist[],int path[],int s[],int n,int v)
{
int i,k;
for(i=0; i<n; i++)
{
if(s[i]==1)
{
k=i;
printf("v%d 到 v%d 的最短路径为：",v,i);
while(k!=v)
{
printf("v%d<-",k);
k=path[k];
}
printf("v%d 路径长度位：%d\n",v,dist[i]);
}
else
printf("v%d路径长度为：%d\n",v,dist[i]);
}
}
void dijkstra(MGraph *G,int v)//G为指向图的邻接矩阵的指针，v是源点的序号
{
int dist[MaxVertexNum],path[MaxVertexNum];//辅助向量dist，其其中一成员表示当前求出的从源点到此成员的最短路径的长度（注：这个路径长度不一定是真的最短路径长度 ，需要不断迭代，到最后才为最短
//path辅助数组，path[i]为存储相应dist[i]最短路径（即源点到vi）上的顶点编号
int s[MaxVertexNum];//s数组用来标记已经找到的最短路径的顶点
int mindis;
int i,j,k;
for(i=0; i<G->n; i++)
{
dist[i]=G->edges[v][i];//距离初始化
s[i]=0; //s数组初始化，0表示未找到最短路径
if(G->edges[v][i]<INF) //路径初始化
path[i]=v;
else
path[i]=-1;
}
s[v]=1; //源点v放入S中
for(i=0; i<G->n; i++)//重复，直到求出v到其余所有顶点的最短路径
{
mindis=INF;
k=v;
for(j=0; j<G->n; j++)//从V-S中选取具有最小距离的顶点vk
{
if(s[j]==0&&dist[j]<mindis)
{
k=j;
mindis=dist[j];
}
}
s[k]=1; //将顶点k加入s中
for(j=0; j<G->n; j++)//修改V-S中顶点的距离dist[j]
{
if(s[j]==0&&G->edges[k][j]<INF&&dist[k]+G->edges[k][j]<dist[j])
{
dist[j]=dist[k]+G->edges[k][j];
path[j]=k;
}
}
}
dist[v]=0;
dispath(dist,path,s,G->n,v);//输出最短路径
}
int main()
{
MGraph x;
int start;
CreateMGraph(&x);
printf("请输入起始顶点：");
scanf("%d",&start);
dijkstra(&x,start);
return 0;
}
六、代码反思
脑残bug 1、scanf里边是不能有其他字符的，比如 scanf(“请输入起始顶点：%d”,&start); 这样非但不能不显示字符，还会影响赋值的过程
