ToB企服应用市场:ToB评测及商务社交产业平台

标题: Dijkstra算法（迪杰斯特拉算法） [打印本页]
作者: 天空闲话    时间: 2024-6-15 02:31
标题: 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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4