Dijkstra算法（迪杰斯特拉算法）
迪杰斯特拉算法通常用在图的最短路径题目上而迷宫的最短路径可以用BFS来做，虽然BFS不能用于带权值的迷宫，但是可以对BFS轻微改进，只必要把判断是否走过的数组改为最短路径的数组，在判断是否可走时判断是否比最短的小即可
Dijkstra步骤如下：
1，初始化一个graph二维数组来存储图的邻接表，一个dis一维数组来存储最短路径，一个check来存储是否走过
2，从出发点开始，将出发点的路径设置为0，也就是disp[出发点] = 0
3，进入循环，每次寻找dis中最小的节点，然后遍历邻接表，如果邻接表的间隔+该点的dis < dis[循环到的点]，那么就迭代循环到的点，最后将最小的那个点check设置为true
while(!end())
{
//寻找最小的点
int min = max_num,min_num = max_num;
for(int i = 1;i <= ::max;++i)
{
if(dis < min_num && !check)
{
min = i;
min_num = dis;
}
}
//从邻接表中寻找这个点可到达的点，并迭代可到达的点的距离
for(int i = 1;i <= ::max;++i)
{
if(graph != max_num)
{
if(dis > dis + graph)
{
dis = dis + graph;//经过最小的那个点到达这个点的距离为dis + graph
}
}
}
//将最小的那个点标记
check = true;
} 4，循环直到全部check都为true即可
也可以直接写一个函数判断
//这里写了一个函数判断是否都被标记
bool end()
{
for(int i = 1;i <= ::max;++i)
{
if(!check)
{
return false;
}
}
return true;
} c++代码如下
#include <bits/stdc++.h>#define max_num 9999using namespace std;int graph;//邻接表，存储图int dis;//存储最短路径bool check;//存储是否被标记int max;//存储最大节点//这里写了一个函数判断是否都被标记
bool end()
{
for(int i = 1;i <= ::max;++i)
{
if(!check)
{
return false;
}
}
return true;
}void dijkstra(int e){ while(!end())
{
//寻找最小的点
int min = max_num,min_num = max_num;
for(int i = 1;i <= ::max;++i)
{
if(dis < min_num && !check)
{
min = i;
min_num = dis;
}
}
//从邻接表中寻找这个点可到达的点，并迭代可到达的点的距离
for(int i = 1;i <= ::max;++i)
{
if(graph != max_num)
{
if(dis > dis + graph)
{
dis = dis + graph;//经过最小的那个点到达这个点的距离为dis + graph
}
}
}
//将最小的那个点标记
check = true;
}}int main(){ //初始化，memset不可以用INT_MAX赋值，由于INT_MAX为无符号数最大值为1111111111111111，而memset会将其转换为有符号数的补码也就是-1 memset(dis,max_num,sizeof(dis)); memset(check, false,sizeof(check)); memset(graph,max_num,sizeof(graph)); int n; cin >> n >> ::max; int times = n; while(times--) { int x,y,z; cin >> x >> y >> z; graph = z; graph = z; }#if 0 //输出邻接表 for(int i = 0;i <= ::max;++i) { for(int j = 0;j <= ::max;++j) { printf("%5d ",graph); } cout << endl; }#endif //出发点启动 int start; cin >> start; dis = 0; dijkstra(start); //输出每个点到出发点的最短路径 for(int i = 1;i <= ::max;++i) { cout << i << " : " << dis << endl; }}/*10 71 3 21 2 52 4 93 4 33 6 24 6 44 5 85 6 95 7 36 2 71*/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]