首页 / 算法 / 最短路径（迪杰斯特拉算法）
最短路径（迪杰斯特拉算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了最短路径（迪杰斯特拉算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2061字，纯文字阅读大概需要3分钟。
内容图文
源代码：
#include<stdio.h>
#define MaxInt 32767 //表示极大值
#define MVNum 100 //最大顶点数
typedef char VerTexType; //定义数据类型
typedef int ArcType;
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum,arcnum; //图的点数和边数
}AMGraph;
int LocateVex(AMGraph G,char v)//确定V在G中的位置
{
int i;
for(i = 0; i < G.vexnum; i++)
{
if(G.vexs[i] == v) //如果找到，返回其序号
break;
}
return i;
}
int CreateUDN(AMGraph &G)
{
int v1,v2,w,i,j;
printf(“请输入总顶点数和总边数：”);
scanf("%d %d",&G.vexnum,&G.arcnum);
printf(“请输入点的信息：\n”);
for(i = 0; i < G.vexnum; i++)
scanf(" %c",&G.vexs[i]);
for(i = 0;i < G.vexnum;i++) //初始化邻接矩阵
for(j = 0; j < G.vexnum; j++)
G.arcs[i][j]= MaxInt;
for(int k = 0; k < G.arcnum; k++)//构造邻接矩阵
{
printf(“请输入一条边(第%d条边)连接的两个顶点以及权值：”,k+1);
scanf(" %c %c %d",&v1,&v2,&w);//输入一条边依附的顶点及权值
i = LocateVex(G,v1);
j = LocateVex(G,v2);
G.arcs[i][j] = w; //设置权值
G.arcs[j][i] = MaxInt;
}
return 0;
}
void ShortestPath_DIJ(AMGraph G, char v0)
{
int i,v,w,min,k;
bool S[MVNum]; //记录路径
int D[MVNum]; //保存最短路径长度
int p[MVNum][MVNum]; //路径
k = LocateVex(G,v0); //源点下标
for(v = 0; v < G.vexnum; v++) //初始化
{
S[v] = false; //初始为空集
D[v] = G.arcs[k][v];
for(w = 0; w < G.vexnum; w++)
p[v][w] = 0; //设空路径
if(D[v] < MaxInt)
{
p[v][k] = 1;
p[v][v] = 1;
}
}
S[k] = true; //v0加入S
D[k] = 0; //源点到源点距离为0
printf(“最短路径为\n”);
for(i = 1; i < G.vexnum; i++)
{ //主循环，每次求得v0到某个顶点v的最短路径 并加v到集合S中
min = MaxInt;
for(w = 0; w < G.vexnum; w++)
if(!S[w] && D[w] < min)
{
v = w;
min = D[w]; //选择一条当前最短路径，终点为v
}
S[v] = true; //v加入S
for(w = 0; w < G.vexnum; w++) //更新当前最短路径和距离
if(!S[w] && (min + G.arcs[v][w] < D[w]))
{
D[w] = min + G.arcs[v][w]; //更新D[w]
p[w][w] = 1;
}
printf(“D[%d] = %d\n”, i, D[i]);
}
}
int main()
{
char v0;
AMGraph G;
CreateUDN(G);
printf(“请输入源点：\n”);
scanf(" %c",&v0);
ShortestPath_DIJ(G, v0);
return 0;
}
运行例图：
内容总结
以上是互联网集市为您收集整理的最短路径（迪杰斯特拉算法）全部内容，希望文章能够帮你解决最短路径（迪杰斯特拉算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。