• 是大大撒
    了解作者
  • C/C++
    开发工具
  • 18.9MB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2019-07-10 01:18
    上传日期
Dijkstra最短路径 c++ 算法实现
Dijkstra算法c++实现.zip
内容介绍
#include"Dijkstra.h" //构造函数 Graph_DG::Graph_DG(int vexnum, int edge) { //初始化顶点数和边数 this->vexnum = vexnum; this->edge = edge; //为邻接矩阵开辟空间和赋初值 arc = new int*[this->vexnum]; dis = new Dis[this->vexnum]; for (int i = 0; i < this->vexnum; i++) { arc[i] = new int[this->vexnum]; for (int k = 0; k < this->vexnum; k++) { //邻接矩阵初始化为无穷大 arc[i][k] = INT_MAX; } } } //析构函数 Graph_DG::~Graph_DG() { delete[] dis; for (int i = 0; i < this->vexnum; i++) { delete this->arc[i]; } delete arc; } // 判断我们每次输入的的边的信息是否合法 //顶点从1开始编号 bool Graph_DG::check_edge_value(int start, int end, int weight) { if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) { return false; } return true; } void Graph_DG::createGraph() { cout << "请输入每条边的起点和终点(顶点编号从1开始)以及其权重" << endl; int start; int end; int weight; int count = 0; while (count != this->edge) { cin >> start >> end >> weight; //首先判断边的信息是否合法 while (!this->check_edge_value(start, end, weight)) { cout << "输入的边的信息不合法,请重新输入" << endl; cin >> start >> end >> weight; } //对邻接矩阵对应上的点赋值 arc[start - 1][end - 1] = weight; //无向图添加上这行代码 //arc[end - 1][start - 1] = weight; ++count; } } void Graph_DG::print() { cout << "图的邻接矩阵为:" << endl; int count_row = 0; //打印行的标签 int count_col = 0; //打印列的标签 //开始打印 while (count_row != this->vexnum) { count_col = 0; while (count_col != this->vexnum) { if (arc[count_row][count_col] == INT_MAX) cout << "∞" << " "; else cout << arc[count_row][count_col] << " "; ++count_col; } cout << endl; ++count_row; } } void Graph_DG::Dijkstra(int begin) { //首先初始化我们的dis数组 int i; for (i = 0; i < this->vexnum; i++) { //设置当前的路径 dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1); dis[i].value = arc[begin - 1][i]; } //设置起点的到起点的路径为0 dis[begin - 1].value = 0; dis[begin - 1].visit = true; int count = 1; //计算剩余的顶点的最短路径(剩余this->vexnum-1个顶点) while (count != this->vexnum) { //temp用于保存当前dis数组中最小的那个下标 //min记录的当前的最小值 int temp = 0; int min = INT_MAX; for (i = 0; i < this->vexnum; i++) { if (!dis[i].visit && dis[i].value < min) { min = dis[i].value; temp = i; } } //cout << temp + 1 << " "<<min << endl; //把temp对应的顶点加入到已经找到的最短路径的集合中 dis[temp].visit = true; ++count; for (i = 0; i < this->vexnum; i++) { //注意这里的条件arc[temp][i]!=INT_MAX必须加,不然会出现溢出,从而造成程序异常 if (!dis[i].visit && arc[temp][i] != INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) { //如果新得到的边可以影响其他为访问的顶点,那就就更新它的最短路径和长度 dis[i].value = dis[temp].value + arc[temp][i]; dis[i].path = dis[temp].path + "-->v" + to_string(i + 1); } } } } void Graph_DG::print_path(int begin) { string str; str = "v" + to_string(begin); cout << "以" << str << "为起点的图的最短路径为:" << endl; for (int i = 0; i != this->vexnum; i++) { if (dis[i].value != INT_MAX) cout << dis[i].path << "=" << dis[i].value << endl; else { cout << dis[i].path << "是无最短路径的" << endl; } } }
评论
    相关推荐
    • Djstra.rar
      迪杰斯特拉算法例程,采用C++语言描述 适用于初学者学习交流使用
    • qpopper2.53.tar.Z
      pop3 server
    • imap-4.7.tar.Z
      被广泛使用的email服务器 /IMAPD/POPD
    • 53308459Add_Dlt_TabCtrl.rar
      Tab分页的删除和添加,实现分页动态的管理。
    • ns-allinone-2.33.tar.gz
      ns2.33这是目前比较新的ns2版本,欢迎下载
    • NetVideoActiveX23.rar
      海康威视 网络监控插件 带有例子 和开发的dll文件,非常易用
    • UR054g_(R01).zip
      法国inventel的ur054g(r01)v1.1的无线网卡驱动。
    • eat.rar
      外卖叫餐系统,采用ACCESS数据库,有完整天的后台管理系统
    • KSTVTUNE.ZIP
      装摄像头驱动需要用到的文件。Microsoft DirectX 9 SDK
    • Skin++.rar
      知名的Skin++界面库,内含所有库文件和大量皮肤文件.该库使用方便,可以减少您美化程序的痛苦.本版是破解版,没有注册提示.但只供学习研究使用哦,不要用在商业用途.