加入CODE CHINA

· 不限速    · 不限空间    · 不限人数    · 私仓免费

免费加入
README.md

离散数学

目录介绍:

  • Graph —— 图论部分文件
  • Graph/GraphTypeJudger.cpp - 图类别判断
  • Graph/Dijkastra.cpp - 最短路算法(普通方法)

程序介绍:

1、图类别判断(Graph\GraphTypeJudger.cpp)

1、初始化图(这里偷了个懒,主对角线初始化为1,其实这样是不对滴)
2、可达矩阵P计算(利用逻辑运算)
逻辑运算来计算可达矩阵 递归定义
3、判断图类别

2、 Dijkastra算法(最短路算法)

1、输入节点个数,输入邻接权矩阵(邻接的通路数换为权值)
2、定义一个长度为节点个数的bool数组判断路径是否走过过(走过设置为true)
3、定义一个Route数组储存到各节点的最短距离(初始化全为-1,规定-1为无穷远,显然定义无穷大的是不够合理的)
4、默认从V0开始(即V0到各点的最短距离),定义一个值记录上一步的节点。
5、对于不在Set(步骤2中定义的节点数组)判断其与上一步操作节点的最短距离比较,选取较小者替代之。
6、重复第五步知道Set中全为true。

测试输入:

0 3 4 0 0 0
3 0 6 10 0 0
4 6 0 3 2 0
0 10 3 0 2 2
0 0 2 2 0 4
0 0 0 2 4 0

测试结果:

0 3 4 0 0 0
3 0 6 10 0 0
4 6 0 3 2 0
0 10 3 0 2 2
0 0 2 2 0 4
0 0 0 2 4 0
最短路算法 测试结果

项目简介

当前项目暂无项目简介

发行版本

当前项目没有发行版本

贡献者 1

东方怂天 @qq_19577209

开发语言

  • C++ 89.9 %
  • C 10.1 %