单源最短路径Dijkstra算法C++实现
// 单源最短路径Dijkstra算法实现.cpp : Defines the entry point for the console application.
#include &stdafx.h&
#include&iostream&
#define MAX 200
#define Infinity 65535
//边尾节点信息结构体
struct edgeNode
&&& //尾接点序号
&& //边权值
&edgeNode * //其下一条邻接边尾节点指针
//节点信息结构体
struct vexNode
&& //节点名称
&edgeNode * //与其相连的边的尾节点链表指针
struct Queue
& //队列中节点序号
& //以此为尾节点的边的权值
//优先队列
Queue priQue[MAX];
//节点数组
vexNode adjlist[MAX];
//指定源点到节点i的最短路径花费
int lowcost[MAX];
//指定源点到节点i路径中，节点i的前驱节点序号
int parent[MAX];
//建立图邻接表
void createGraph(vexNode *adjlist,int *parent,int * lowcost,const int n,const int e)
&for(i=1;i&=n;i++)
& cout&&&请输入节点&&&i&&&的名称：&;
& cin&&adjlist[i].
& adjlist[i].link = NULL;
& lowcost[i] = I
& parent[i] =
&edgeNode *p1;
&& int v1,v2;
&for(i=1;i&=e;i++)
& cout&&&请输入边&&&i&&&的起始节点与尾节点序号：&;
& cin&&v1&&v2;
& p1 = (edgeNode*)malloc(sizeof(edgeNode));
& p1-&no = v2;
& cout&&&此边的权值：&;
& cin&&p1-&
& p1-&next = adjlist[v1].
& adjlist[v1].link = p1;
//当插入节点到优先队列时，保持队列优先性
void keep_min_heap(Queue *priQue,int &num,const int k)
&int l = 2*k;
&int r = 2*k + 1;
&int smallest =
&if(l&=num&&priQue[l].cost&priQue[k].cost)
& smallest =
&if(r&=num&&priQue[r].cost&priQue[smallest].cost)
& smallest =
&if(smallest != k)
& Queue temp = priQue[smallest];
& priQue[smallest] = priQue[k];
& priQue[k] =
& keep_min_heap(priQue,num,smallest);
//插入节点到优先队列时并且保持队列优先性
void heap_insert(Queue *priQue,int &num,int no,int cost)
&priQue[num].no =
&priQue[num].cost =
&while(i&1&&priQue[i/2].cost&priQue[i].cost)
& Queue temp = priQue[i];
& priQue[i] = priQue[i/2];
& priQue[i/2] =
& i = i/2;
//取出优先队列的队头元素
Queue heap_extract_min(Queue *priQue,int &num)
&if(num&1)
& return priQue[0];
&Queue min = priQue[1];
&priQue[1] = priQue[num];
&keep_min_heap(priQue,num,1);
//打印指定源点带序号为i的点的最短路径
void print_it(int *parent,vexNode *adjlist,int v)
&if(parent[v] == v)
& cout&&&(&&&v&&&:&&&adjlist[v].info&&&) &;
& print_it(parent,adjlist,parent[v]);
& cout&&&(&&&v&&&:&&&adjlist[v].info&&&) &;
int _tmain(int argc, _TCHAR* argv[])
&cout&&&请输入案例的个数：&;
&while(cases--)
& int n,e;
& cout&&&请输入节点数：&;
& cout&&&请输入边数：&;
& //队列中的元素，初始为0
& int num = 0;
& //创建邻接表
& createGraph(adjlist,parent,lowcost,n,e);
& cout&&&从哪个节点开始：&;
& cin&&v0;
& int v =v0;
& lowcost[v0] = 0;
& for(i=1;i&n;i++)
&& edgeNode *p = adjlist[v0].
&& while(p != NULL)
&&& if(lowcost[v0] + p-&cost&lowcost[p-&no])
&&&& lowcost[p-&no] = lowcost[v0] + p-&
&&&& parent[p-&no] = v0;
&&&& heap_insert(priQue,num,p-&no,lowcost[p-&no]);
&&& p = p-&
&& queue = heap_extract_min(priQue,num);
&& v0 = queue.
& for(i=1;i&=n;i++)
&& mincost = 0;
&& cout&&&从点&&&adjlist[v].info&&&开始到&&&adjlist[i].info&&&的最短路径为：&&&
&& print_it(parent,adjlist,i);
&& cout&&&距离为：&&&lowcost[i]&&
&system(&pause&);
&return 0;
--------------------------------------------------程序测试-----------------------------------------------------&&& &&&
&&&&&&&&&&&&&&&&&
请输入案例的个数：1
请输入节点数：5
请输入边数：10
请输入节点1的名称：a
请输入节点2的名称：b
请输入节点3的名称：c
请输入节点4的名称：d
请输入节点5的名称：e
请输入边1的起始节点与尾节点序号：1 2
此边的权值：10
请输入边2的起始节点与尾节点序号：1 4
此边的权值：5
请输入边3的起始节点与尾节点序号：2 3
此边的权值：1
请输入边4的起始节点与尾节点序号：2 4
此边的权值：2
请输入边5的起始节点与尾节点序号：3 5
此边的权值：4
请输入边6的起始节点与尾节点序号：4 2
此边的权值：3
请输入边7的起始节点与尾节点序号：4 3
此边的权值：9
请输入边8的起始节点与尾节点序号：4 5
此边的权值：2
请输入边9的起始节点与尾节点序号：5 1
此边的权值：7
请输入边10的起始节点与尾节点序号：5 3
此边的权值：6
从哪个节点开始：1
从点a开始到a的最短路径为：
从点a开始到b的最短路径为：
(1:a) (4:d) (2:b)
从点a开始到c的最短路径为：
(1:a) (4:d) (2:b) (3:c)
从点a开始到d的最短路径为：
(1:a) (4:d)
从点a开始到e的最短路径为：
(1:a) (4:d) (5:e)
请按任意键继续. .
作者 heyongluoyao8最短路径算法实现(C++)
// Dijkstra.cpp : Defines the entry point for the console
application.
#include "stdafx.h"
#include "iostream"
#include &stdio.h&
6&&&&&&&&&&&&&
//定义结点个数
int main(int argc, char* argv[])
&int Cost[N][N],Dist[N],rDist[N];
&int temp=1000;
&int mark=0,fn[N]={0};
&int l=0,s[N];
&int i,j,k;
&for(i=0;i&N;i++)
& for(j=0;j&N;j++)
& {Cost[i][j]=1000;}
&for (i=0;i&N;i++)
&{Dist[i]=1000;s[i]=0;}&&
//给Dist赋初始值
&for (i=0;i&N;i++)
Cost[i][i]=1000;&&&&&
//自身结点之间的距离设为最大
Cost[0][1]=5;Cost[0][3]=8;
&Cost[1][2]=12;Cost[1][4]=10;
&Cost[2][4]=2;Cost[2][5]=13;
&Cost[3][1]=14;Cost[3][4]=21;
&Cost[4][5]=9;
&cout&&"路径矩阵如下："&&'\n';
&for (i=0;i&N;i++)
& for (j=0;j&N;j++)
cout&&setw(4)&&Cost[i][j]&&"
& cout&&'\n';
&}&&&&&&&&&&&&&&&&&&&&&&&
//输出各个结点间的路径长度
&cout&&'\n';
&Dist[0]=0;
&while (mark&N)
k=l;&&&&&&&&&&&&&&&&
//确定节点
& for (i=0;i&N;i++)
(Dist[i]&Cost[k][i]+Dist[k])
Dist[i]=Cost[k][i]+Dist[k];
}&&&&&&&&&&&&&&&&&&&
//比较路径长度
& for (i=0;i&N;i++)
(s[i]==0&&Dist[i]&temp)
&& {temp=Dist[i];l=i;}
}&&&&&&&&&&&&&&&&&&
//选择下一结点
& temp=1000;
s[l]=1;&&&&&&&&&&&&
mark++;&&&&&&&&&&&
&cout&&"从起始点到其他各点的最短路径如下："&&'\n';
&for(i=0;i&N;i++)
cout&&Dist[i]&&","&&fn[i]&&'\n';
&}&&&&&&&&&&&&&&&&&&&&&&&&
//输出计算结果
&return 0;
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。c++查询最短路径示例
来源：易贤网&& 阅读：418 次&&日期： 15:41:39
温馨提示：易贤网小编为您整理了“c++查询最短路径示例”,方便广大网友查阅！
这篇文章主要介绍了c++查询最短路径示例,需要的朋友可以参考下
//shortest_path.c
#include//用file
#include//可用gets(),puts()
#include"shortest_path.h"
#define MAX 32767
#define MENU "欢迎进入导航系统!n==========菜单===========n0、载入北外地图n1、建立地图n2、查询最短路径n3、退出n==========菜单===========n"
const char *filepath1="D:spots.dat";
const char *filepath2="D:paths.dat";
int load1()
fp=fopen(filepath1,"r");
if(fp==NULL){printf("spots文件打开异常，读取失败");return -1;}
fread(&map.spotnum,sizeof(int),1,fp);
fread(map.spot[i].name,sizeof(char),10,fp);
fread(map.spot[i].intro,sizeof(char),20,fp);
fclose(fp);
int load2()
fp=fopen(filepath2,"r");
if(fp==NULL){printf("paths文件打开异常，读取失败");return -1;}
fread(&map.pathmatrix,sizeof(int),1,fp);
fread(&map.pathmatrix[i][j],sizeof(int),1,fp);
fclose(fp);
void loadmap()
if(load1()==0)
printf("spot读入成功n");
printf("spot读入失败n");
if(load2()==0)
printf("path读入成功n");
printf("path读入失败n");
void drawmap()//直接输入
char s1[10],s2[10];
printf("共有几个景点?(&=20)");//map.spotmun
fflush(stdin);
scanf("%d",&map.spotnum);
printf("共有几条景点与景点之间直接相连的路径?");//map.pathnum
fflush(stdin);//清空键盘缓冲区，在"stdio.h"中
scanf("%d",&map.pathnum);
if(a==b)map.pathmatrix[a][b]=0;
else map.pathmatrix[a][b]=MAX;
printf("请输入第%d个景点的名称(&=10letters)",i+1);
fflush(stdin);
gets(map.spot[i].name);
printf("请输入第%d个景点的介绍(&=20letters)",i+1);
fflush(stdin);
gets(map.spot[i].intro);
}//输入景点名字和简介map.spot[].map.spot[].intro
printf("请输入第%d条路径的起点",i+1);
fflush(stdin);
if(!strcmp(map.spot[a].name,s1))//查找景点编号
if(a==map.spotnum)printf("不存在此景点，请重新输入。n");
}while(a==map.spotnum);
printf("请输入第%d条路径的终点",i+1);
fflush(stdin);
if(!strcmp(map.spot[b].name,s2))
if(b==map.spotnum)printf("不存在此景点，请重新输入。n");
}while(b==map.spotnum);
printf("请输入第%d条路径的长度",i+1);
fflush(stdin);
scanf("%d",&map.pathmatrix[a][b]);
map.pathmatrix[b][a]=map.pathmatrix[a][b];//输入路径长度
void shortestpath()//最短路径，输入起点终点输出路径和路程
struct stspath spath[20];
int s,t,v,w,
char s1[10],s2[10];
int pathorder[20];
struct stspath *p;//pathorder
printf("请输入起点");//查找起点的景点编号
fflush(stdin);
if(!strcmp(map.spot[s].name,s1))
if(s==map.spotnum)printf("不存在此景点，请重新输入。n");
}while(s==map.spotnum);
printf("请输入终点");//查找终点的景点编号
fflush(stdin);
if(!strcmp(map.spot[t].name,s2))
if(t==map.spotnum)printf("不存在此景点，请重新输入。n");
}while(t==map.spotnum);
spath[v].length=MAX;
spath[v].in=0;
spath[s].in=1;
spath[s].length=0;
spath[s].pior=NULL;
while(v!=t){
if((!spath[w].in)&&(spath[w].length&spath[v].length+map.pathmatrix[v][w])){
spath[w].length=spath[v].length+map.pathmatrix[v][w];
spath[w].pior=&spath[v];
if((!spath[w].in)&&(spath[w].length
min=spath[w].
spath[v].in=1;
printf("最短路径长度为%d,最短路径为：n",spath[t].length);//print path
for(v=0,p=&spath[t];p-&pior!=NULL;p=p-&pior)
pathorder[v]=p-
pathorder[v]=s;
for(;v&=0;v--)
printf("%10s",map.spot[pathorder[v]].name);
void main()
int menu=1;
printf(MENU);
while(menu!=3)
printf("n请输入您的选项(数字)n");
fflush(stdin);
scanf("%d",&menu);
switch (menu)
case 0: loadmap();printf("n北外地图载入完成n");
case 1: drawmap();printf("n新建完成n");
case 2: shortestpath();printf("n查询完成完成n");
printf("谢谢使用!");
2. [文件] shortest_path.h ~ 430B 下载(2)
#ifndef _SHORTEST_PATH_H_
#define _SHORTEST_PATH_H_
struct stspot{//景点的顶点
char name[11];//景点名称no more than 10
char intro[20];//景点介绍no more than 20
struct stmap{//整个无向网
stspot spot[20];//点，景点向量
int pathmatrix[20][20];//边，路径的邻接矩阵
struct stspath//求最短路径时的景点数组
// can be boolen
更多信息请查看
更多信息请查看
【】&&&&&【点此处查询各地各类考试咨询QQ号码及交流群】
易贤网手机网站地址：
由于各方面情况的不断调整与变化，易贤网提供的所有考试信息和咨询回复仅供参考，敬请考生以权威部门公布的正式信息和咨询为准！
相关阅读 & & &
&&& &nbsp&nbsp&nbsp会员注册
本站不参与评论！（）
自觉遵守：爱国、守法、自律、真实、文明的原则
尊重网上道德，遵守中华人民共和国各项有关法律法规
严禁发表危害国家安全，破坏民族团结、国家宗教政策和社会稳定，含侮辱、诽谤、教唆、淫秽等内容的评论
承担一切因您的行为而直接或间接导致的民事或刑事法律责任
您在本站发表的评论，本站有权保留、转载、引用或者删除
参与本评论即表明您已经阅读并接受上述条款网站已改版，请使用新地址访问：
GA 遗传算法 解决最短路径 用C++来实现其功能
基于 的 问题 Mathimatics-Numerical algorithms 数值 /人工智能 259万源代码下载-
&文件名称: GA& & [
& & & & &&]
&&所属分类:
&&开发工具: Visual C++
&&文件大小: 2 KB
&&上传时间:
&&下载次数: 109
&&提 供 者:
&详细说明：遗传算法 解决最短路径 用C++来实现其功能
基于遗传算法的最短路径问题-Genetic algorithms to solve shortest path with C++ to achieve their function based on genetic algorithm shortest path problem
文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&[]:和说明完全不符
&近期下载过的用户:
&&&&&&&&&&&&&&&&&&&&&[]
&相关搜索:
&输入关键字，在本站259万海量源码库中尽情搜索：
&[] - 遗传算法解决最短路径问题matlab实现
&[] - 弗洛伊德算法 求两点最短路径 （c++）图用邻接矩阵表示
&[] - 基于遗传算法的最短路径计算
程序简洁 速度很快 界面不是很完善
&[] - 基于二进制和实数编码的遗传算法，很好用，肯定能调通
&[] - 本文中利用遗传算法求解的问题为最短路径，该问题可描述为：在某大学校园内有多个场所，各场所之间有一个相关的距离cij ，目标就是要寻找一条从指定的起点 s 到指定的终点 t 的一条路径，使总距离最小。
&[] - 非线性规划的简单遗传算法 由清华刘宝碇教授的实验室发布 将头文件放好 修改即可使用
&[] - 遗传算法求解最短路径，效果还是可以的大家可以下载实验。
&[] - 基于遗传算法解决旅行商问题的vc++源码。
&[] - C++实现的，遗传算法解决背包问题，很经典
&[] - 求解tsp问题的遗传算法源代码。利用这个源程序可以更清晰的知道旅行商问题是如何实现最优化。