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