Dijkstra算法（迪杰斯特拉算法）

迪杰斯特拉算法通常用在图的最短路径题目上
而迷宫的最短路径可以用BFS来做，虽然BFS不能用于带权值的迷宫，但是可以对BFS轻微改进，只必要把判断是否走过的数组改为最短路径的数组，在判断是否可走时判断是否比最短的小即可
Dijkstra步骤如下：
1，初始化一个graph二维数组来存储图的邻接表，一个dis一维数组来存储最短路径，一个check来存储是否走过
2，从出发点开始，将出发点的路径设置为0，也就是disp[出发点] = 0
3，进入循环，每次寻找dis中最小的节点，然后遍历邻接表，如果邻接表的间隔+该点的dis < dis[循环到的点]，那么就迭代循环到的点，最后将最小的那个点check设置为true

1. while(!end())
2.     {
3.         //寻找最小的点
4.         int min = max_num,min_num = max_num;
5.         for(int i = 1;i <= ::max;++i)
6.         {
7.             if(dis[i] < min_num && !check[i])
8.             {
9.                 min = i;
10.                 min_num = dis[i];
11.             }
12.         }
14.         //从邻接表中寻找这个点可到达的点，并迭代可到达的点的距离
15.         for(int i = 1;i <= ::max;++i)
16.         {
17.             if(graph[min][i] != max_num)
18.             {
19.                 if(dis[i] > dis[min] + graph[min][i])
20.                 {
21.                     dis[i] = dis[min] + graph[min][i];//经过最小的那个点到达这个点的距离为dis[min] + graph[min][i]
22.                 }
23.             }
24.         }
25.         //将最小的那个点标记
26.         check[min] = true;
27.     }

复制代码

4，循环直到全部check都为true即可
也可以直接写一个函数判断

1. //这里写了一个函数判断是否都被标记
2. bool end()
3. {
4.     for(int i = 1;i <= ::max;++i)
5.     {
6.         if(!check[i])
7.         {
8.             return false;
9.         }
10.     }
11.     return true;
12. }

复制代码

 c++代码如下

1. #include <bits/stdc++.h>#define max_num 9999using namespace std;int graph[max_num][max_num];//邻接表，存储图int dis[max_num];//存储最短路径bool check[max_num];//存储是否被标记int max;//存储最大节点//这里写了一个函数判断是否都被标记
2. bool end()
3. {
4.     for(int i = 1;i <= ::max;++i)
5.     {
6.         if(!check[i])
7.         {
8.             return false;
9.         }
10.     }
11.     return true;
12. }void dijkstra(int e){    while(!end())
13.     {
14.         //寻找最小的点
15.         int min = max_num,min_num = max_num;
16.         for(int i = 1;i <= ::max;++i)
17.         {
18.             if(dis[i] < min_num && !check[i])
19.             {
20.                 min = i;
21.                 min_num = dis[i];
22.             }
23.         }
25.         //从邻接表中寻找这个点可到达的点，并迭代可到达的点的距离
26.         for(int i = 1;i <= ::max;++i)
27.         {
28.             if(graph[min][i] != max_num)
29.             {
30.                 if(dis[i] > dis[min] + graph[min][i])
31.                 {
32.                     dis[i] = dis[min] + graph[min][i];//经过最小的那个点到达这个点的距离为dis[min] + graph[min][i]
33.                 }
34.             }
35.         }
36.         //将最小的那个点标记
37.         check[min] = true;
38.     }}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 71 3 21 2 52 4 93 4 33 6 24 6 44 5 85 6 95 7 36 2 71*/

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。