最短路径-----迪杰特斯拉算法
算法 路径 ----- 特斯拉 最短
2023-09-14 09:13:37 时间
无向图
最短路径:两顶点之间经历的边数最少的路径
网图
最短路径:两顶点之间经历的边上的权值之和最短的路径
迪杰特斯拉算法思路:按路径长度递增的次序产生最短路径的算法
图解:
数据结构
伪代码
图解:
伪代码
代码解释:
邻接矩阵实现
#include<iostream>
using namespace std;
#define Max 10//最大顶点数
#define MANY 65535
class Graph
{
private:
int verNum;//顶点个数
int arcNum;//边的个数
public:
int ver[Max];//顶点数组
int arc[Max][Max];//网图的邻接矩阵
public:
Graph(int v[],int n,int e);
int getVernum()
{
return verNum;
}
int getArcnum()
{
return arcNum;
}
};
Graph::Graph(int v[],int n,int e)
{
verNum = n;
arcNum = e;
for (int i = 0; i < verNum; i++)
ver[i] = v[i];
for (int i = 0; i < verNum; i++)
{
for (int j = 0; j < verNum; j++)
{
if (i == j)
{
arc[i][j] = 0;
}
else {
arc[i][j] = MANY;
}
}
}
cout << "请输入每条边依附的两个顶点和权值:" << endl;
int vi=0, vj=0,k=0;
for (int i = 0; i <arcNum; i++)
{
cin >> vi >> vj>>k;
arc[vi][vj] = k;
}
}
//查找当前没有放入s中的最小顶点---dist数组 s数组 顶点数
int findMinDist(int dist[], int s[], int verNum)
{
int min = -1;
for (int i = 0; i < verNum; i++)
{
if (s[i] == 0)//当前节点没有被放入S数组
{
min = i;//假设当前节点为最小顶点
for (int j = 0; j < verNum; j++)
{
if (s[j] == 0)
{
if (dist[min] > dist[j])//当前j节点对应dist数组中的值更小,即距离更短
{
min = j;
}
}
}
}
}
return min;
}
//打印最短路径
void display(int dist[], int path[],int s[], Graph* p,int startV)
{
int RightPath[Max] = { 0 };
for (int i = 0; i < p->getVernum(); i++)
{
cout << "源点到" << i << "顶点的最短路径:";
cout << 0;
int num = 0;//计算最短路径有几个顶点
RightPath[num++] = i;
int t = path[i];
while (t != 0)
{
RightPath[num++] = t;
t = path[t];
}
//逆序打印数组,得到最短路径
for (int j= num - 1; j>= 0; j--)
{
cout << RightPath[j];
}
cout << endl;
}
}
//迪杰斯特拉算法:startV----源点,计算的起点
void Dijkstra(Graph* p, int startV)
{
int dist[Max];//存放最短路径的长度
int path[Max];//存放最短路径的下标
int s[Max] = { 0 };//S数组中存放的是已经计算出最短路径的节点
//初始化dist数组和path数组
for (int i = 0; i < p->getVernum(); i++)
{
//当s数组中只有一个源点的时候,那么最短路径就是当前源点到U集合中各顶点的距离
dist[i] = p->arc[startV][i];
//s数组一开始只有一个源点,例如源点为0,0一开始只能到U集合的1 2 3顶点,因此到1,2,3顶点的前一个节点下标为0,因为到4,5,6顶点距离为无穷大,所以无法到达4,5,6,path数组中存放的值为-1
if (dist[i] != MANY)
{
//起点为源点
path[i] = startV;
}
else
{
//源点到达不了该顶点,没有起点
path[i] = -1;
}
}
//源点放入集合s
s[startV] = 1;
//计算当前已经放入S集合中的顶点个数,即已经求出最短路径的节点个数
int num = 1;//一开始只有源点
int min = 0;//最小顶点的下标
while (num < p->getVernum())
{
//1.查找当前dist数组中s[i]为0的最小顶点
min = findMinDist(dist, s, p->getVernum());
//2.将最小顶点放入集合S中
s[min] = 1;
//3.新顶点加入后,是否会产生更优解,如果有就更新dist和path数组
for (int i = 0; i < p->getVernum(); i++)
{
if (s[i] == 0 && dist[i] > dist[min] + p->arc[min][i])
{
//更新
dist[i] = dist[min] + p->arc[min][i];//修改到源点到i顶点最短路径
path[i] = min;//到达当前i顶点最短路径的前一个起点更新
}
}
num++;
}
cout << "path数组打印:" << endl;
for (int i = 0; i < p->getVernum(); i++)
cout << path[i] << "\t";
cout << endl;
cout << "dist数组打印:" << endl;
for (int i = 0; i < p->getVernum(); i++)
cout << dist[i] << "\t";
cout << endl;
//打印起始点到各顶点的最短路径
cout << "打印最短路径:" << endl;
display(dist,path,s, p,startV);
}
//测试----------------------
void test()
{
int v[7] = { 0,1,2,3,4,5,6 };
Graph p(v, 7, 12);
cout << "打印邻接矩阵" << endl;
for (int i = 0; i < p.getVernum(); i++)
{
for (int j = 0; j < p.getVernum(); j++)
{
cout << p.arc[i][j]<<"\t";
}
cout << endl;
}
Dijkstra(&p, 0);
}
int main()
{
test();
system("pause");
return 0;
}
相关文章
- 【Python算法】分类与预测——logistic回归分析
- Java实现 蓝桥杯VIP 算法训练 乘法表
- 最短路径—Dijkstra算法和Floyd算法
- (算法)无向图最短路径的数目
- flink Transitive Closure算法,实现寻找新的可达路径
- 基于用户投票的排名算法(二):Reddit
- 【C#代码实战】群蚁算法理论与实践全攻略——旅行商等路径优化问题的新方法
- atitit.md5算法的原理 与 总结
- EL之DT&RF&GBT:基于三种算法(DT、RF、GBT)对titanic(泰坦尼克号)乘客数据集进行二分类(是否获救)预测并对比各自性能
- Android 用三个线程依次打印10个abc的算法题
- 基于A*算法自动引导车的路径规划(Matlab代码实现)
- 基于蚁群算法求解运钞车路径规划问题(Matlab代码实现)
- 基于蚁群算法的车辆路径规划问题的研究(Matlab代码实现)
- 【路径优化】基于帝企鹅算法求解TSP问题(Matlab代码实现)
- 基于球向量的粒子群优化(SPSO)算法在无人机路径规划中的实现(Matlab代码实现)
- 基于A*算法的多机器人图形路径规划解决策略(Matlab代码实现)
- m基于多用户MIMO系统的分布式可重构注水算法的matlab仿真
- m基于ESN+BP神经网络的数据预测算法matlab仿真,测试数据为太阳黑子变化数据
- 剑指 Offer 11. 旋转数组的最小数字-优化算法
- 2304. 网格中的最小路径代价-动态规划+贪心算法
- 最短路径-迪杰斯特拉(Dijkstra)算法
- 设计一个算法,输出从u到v的全部最短路径(採用邻接表存储)
- 10分钟弄懂Raft算法
- 经典树与图论(最小生成树、哈夫曼树、最短路径问题---Dijkstra算法)
- 路径规划算法:Dijkstra算法 - 附代码
- 路径规划算法 python 实现