迪杰斯特拉算法通常用在图的最短路径问题上
而迷宫的最短路径可以用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[i] < min_num && !check[i])
{
min = i;
min_num = dis[i];
}
}
//从邻接表中寻找这个点可到达的点,并迭代可到达的点的距离
for(int i = 1;i <= ::max;++i)
{
if(graph[min][i] != max_num)
{
if(dis[i] > dis[min] + graph[min][i])
{
dis[i] = dis[min] + graph[min][i];//经过最小的那个点到达这个点的距离为dis[min] + graph[min][i]
}
}
}
//将最小的那个点标记
check[min] = true;
}
4,循环直到所有check都为true即可
也可以直接写一个函数判断
//这里写了一个函数判断是否都被标记
bool end()
{
for(int i = 1;i <= ::max;++i)
{
if(!check[i])
{
return false;
}
}
return true;
}
c++代码如下
#include <bits/stdc++.h>
#define max_num 9999
using namespace std;
int graph[max_num][max_num];//邻接表,存储图
int dis[max_num];//存储最短路径
bool check[max_num];//存储是否被标记
int max;//存储最大节点
//这里写了一个函数判断是否都被标记
bool end()
{
for(int i = 1;i <= ::max;++i)
{
if(!check[i])
{
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[i] < min_num && !check[i])
{
min = i;
min_num = dis[i];
}
}
//从邻接表中寻找这个点可到达的点,并迭代可到达的点的距离
for(int i = 1;i <= ::max;++i)
{
if(graph[min][i] != max_num)
{
if(dis[i] > dis[min] + graph[min][i])
{
dis[i] = dis[min] + graph[min][i];//经过最小的那个点到达这个点的距离为dis[min] + graph[min][i]
}
}
}
//将最小的那个点标记
check[min] = 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[x][y] = z;
graph[y][x] = z;
}
#if 0
//输出邻接表
for(int i = 0;i <= ::max;++i)
{
for(int j = 0;j <= ::max;++j)
{
printf("%5d ",graph[i][j]);
}
cout << endl;
}
#endif
//起点启动
int start;
cin >> start;
dis[start] = 0;
dijkstra(start);
//输出每个点到起点的最短路径
for(int i = 1;i <= ::max;++i)
{
cout << i << " : " << dis[i] << endl;
}
}
/*
10 7
1 3 2
1 2 5
2 4 9
3 4 3
3 6 2
4 6 4
4 5 8
5 6 9
5 7 3
6 2 7
1
*/