资源简介
数据结构_导航最短路径查询课外实践,迪杰斯特拉算法 弗洛伊德算法

代码片段和文件信息
#include
#include
using namespace std;
//*******************图的邻接矩阵表示*************
typedef struct
{
char*vexs; //顶点向量;
int **arcs; //邻接矩阵;
int vexnumarcnum; //图的当前顶点数和弧数;
}MGraph;
//***********************************************
//***********查找u顶点在顶点向量中的位置*********
int locate(MGraph Gchar u)
{
int i;
int k;
for(i=0;i {
if(u==G.vexs[i])
{
k=i;
break;
}
}
return k;
}
//创建有向图的邻接矩阵存储结构
//此时.adj存储弧的长度;
void createMGraph(MGraph&mg)
{
int ij;
ifstream fin(“Floyd.txt“ios::in);//文件流类对象
if(!fin)//判断文件流类对象是否创建成功
{
cout<<“文件无法打开!“< exit(0);
}
fin>>mg.vexnum>>mg.arcnum;//从文件输入顶点数和边数
mg.vexs=new char[mg.vexnum];//开辟空间存储各顶点
for( i=0;i {
fin>>mg.vexs[i];//从文件输入顶点
}
//*************开辟空间存储邻接矩阵*************
mg.arcs=new int*[mg.vexnum];
for(i=0;i {
mg.arcs[i]=new int[mg.vexnum];
}
//*****************end************************
for(i=0;i {
for(j=0;j {
fin>>mg.arcs[i][j];
cout< }
cout< }
}
//************求v0到其余各顶点的最短距离及路径*****************
void ShortestPath_DIJ(MGraph&Gint v0int *&Pint*&D)
{
int ikjmin;
bool *final=new bool[G.vexnum];//标志数组
P=new int [G.vexnum];//全局变量存储路径
D=new int [G.vexnum];//全局变量存储最短距离
//初始化;
for(i=0;i {
final[i]=false;
D[i]=G.arcs[v0][i];
P[i]=v0;
}
final[v0]=true;//表示始点已求出最短路径;
for(i=1;i {
//找一个顶点从v0到该顶点距离最短
min=1000;//min初始化为最大值
for(j=0;j {
if(!final[j]&&min>D[j])
{
min=D[j];
k=j;//记录当前距离最短的顶点
}
}
final[k]=true;//表示已求出v0到k的最短距离
//当前最短路径更新
for(j=0;j {
if(!final[j]&&(min+G.arcs[k][j]) {
D[j]=G.arcs[k][j]+min;
P[j]=k;
}
}
}
}
//输出最短路径(递归算法);//b到v0的路径
void explainPathRecursionDIJ(MGraph&Gint *pathint v0int b)
{
int k;
if(v0==b)
{
k=v0;
cout< }
else
{
explainPathRecursionDIJ(Gpathpath[v0]b);
k=v0;
cout< }
}
//输出最短路径及长度;//b到其余各顶点的路径
void printPathDIJ(MGraph&Gint *pathint*dint b)
{
int n=G.vexnum;
int i;
cout<<“始点“<<‘\t‘<<“终点“<<‘\t‘<<“最短路径“<<“\t“<<“路径长度“< for(i=0;i {
if(i!=b)
{
cout< explainPathRecursionDIJ(Gpathib);
cout<<“\t\t“< cout< }
}
cout< }
//Floyd算法//求有向网G中各对顶点v和w之间的最短路径
void ShortestPath_FLOYD(MGraph&Gint **&pint **&d)
{
int ijk;
//开辟空间存储最短路径与最短距离(p和d都是二维的)
p=new int *[G.vexnum];
d=new int *[G.vexnum];
for(i=0;i {
p[i]=new int [G.vexnum];
d[i]=new int [G.vexnum];
}
//初始化
for(i=0;i {
for(j=0;j {
p[i][j]=i;//记录初始路径
d[i][j]=G.arcs[i][j];//记录初始路径长度
}
}
//求最短距离和最短路径
for(k=0;k {
for(i=0
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
目录 0 2014-06-07 23:53 导航最短路径查询\
目录 0 2014-06-07 23:53 导航最短路径查询\Debug\
文件 74752 2013-12-27 00:45 导航最短路径查询\Debug\vc60.idb
文件 118784 2013-12-27 00:45 导航最短路径查询\Debug\vc60.pdb
文件 573538 2013-12-27 00:45 导航最短路径查询\Debug\导航最短路经.exe
文件 820400 2013-12-27 00:45 导航最短路径查询\Debug\导航最短路经.ilk
文件 355920 2013-12-27 00:45 导航最短路径查询\Debug\导航最短路经.obj
文件 2098908 2013-12-26 17:30 导航最短路径查询\Debug\导航最短路经.pch
文件 1139712 2013-12-27 00:45 导航最短路径查询\Debug\导航最短路经.pdb
文件 119 2013-12-14 19:35 导航最短路径查询\Floyd.txt
文件 44 2013-12-04 21:14 导航最短路径查询\Floyd2.txt
文件 5238 2013-12-26 17:35 导航最短路径查询\导航最短路经.cpp
文件 3475 2013-12-27 00:45 导航最短路径查询\导航最短路经.dsp
文件 532 2013-12-27 00:46 导航最短路径查询\导航最短路经.dsw
文件 41984 2013-12-27 00:46 导航最短路径查询\导航最短路经.ncb
文件 48640 2013-12-27 00:46 导航最短路径查询\导航最短路经.opt
文件 1192 2013-12-27 00:45 导航最短路径查询\导航最短路经.plg
文件 153600 2014-06-07 23:53 数据结构_导航最短路径查询课外实践报告.doc
- 上一篇:步进电机代码
- 下一篇:惠普D2055d中文说明书
相关资源
- 数据结构年终考题范围和答案 耿国华
- 数据结构 朱战力 习题解答 数据结构
- 数据结构课程设计 6 1 彩票系统
- 教学计划编制系统
- 大数(链表、数组)实现
- 自己写的航空订票系统c 版--数据结构
- 数据结构实验魔王语言
- 航空订票系统_数据结构课程设计
- 多项式求和(数据结构C 版)
- 尚观培训linux董亮老师关于数据结构的
- 数据结构 知识点总结
- 华南理工大学数据结构复习提纲二
- 华南理工大学数据结构复习提纲一
- 数据结构用C 写的停车场系统源代码
- 数据结构(河北科技大学)
- 数据结构考前习题 清华大学出版社
- 数据结构课件(北邮)
- 数据结构实验 基于栈的表达式求值
- 数据结构课程设计——图书管理系统
- 成绩管理系统(数据结构)
- 数据结构-最小通信网问题
- 数据结构课程设计同学通讯录系统
- 数据结构课程设计 公园导游图
- 数据结构殷人昆版的课后答案
- 2006年湖北工业大学409数据结构试题
- 数据结构实验-魔王语言-源码加实验报
- 简单计算器的实现(数据结构)
- 简单计算器的实现(数据结构 修正版
- Fundamentals of Data Structure in C
- 北京邮电大学数据结构历年考研真题
评论
共有 条评论