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[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会将其转换为有符号数的补码也就是-1memset(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
*/