Dijkstra(迪杰斯特拉)算法学习

古城微笑少年丶 2022-06-15 12:28 260阅读 0赞

如果要了解过程http://blog.csdn.net/cjc211322/article/details/24933909

关于路径保存方法http://blog.csdn.net/jinixin/article/details/52247763

算法思想：

首先了解这是一个不可以求负权的单源最短路径算法，以贪心的思想，每次寻找一个距离源点最近且没有标记过的节点，然后标记(注意自己到自己的距离置为0)，对该节点进行松弛操作，如果可以进行，就保存路径（要求路径的话），最后用栈还原路径

题目：

wust oj上的一题：1868

## 1868: 最短路径 ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 23 Accepted: 19  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

有n个城市（编号从1到n），个城市之间都有路连接，切这些路都是单向的。每条路都有相应的长度。各城市之间构成的路网不可能构成环状。没有一条路到达城市1，所有城市都能够到达城市n。城市n不能到达其它任何城市。

## Input ##

第一行包含一个整数n，表示城市数目。

接下来包含n行，每行n个整数。第i行第j列的整数a\[i\]\[j\]表示城市i和城市j的路径长度。

10
    0 2 5 1 0 0 0 0 0 0
    0 0 0 0 12 14 0 0 0 0
    0 0 0 0 6 10 4 0 0 0
    0 0 0 0 13 12 11 0 0 0
    0 0 0 0 0 0 0 3 9 0
    0 0 0 0 0 0 0 6 5 0
    0 0 0 0 0 0 0 0 10 0
    0 0 0 0 0 0 0 0 0 5
    0 0 0 0 0 0 0 0 0 2
    0 0 0 0 0 0 0 0 0 0

## Output ##

第一行输出最短路径长度，形如minlong=最短路径长度值“”。

接下来的一行输出从第1个城市到第n个城市的最短路径上的所有城市。（详见样例）

minlong=19
    1 3 5 8 10

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    int p[105][105],path[105];
    int dis[105],vis[105],n;
    const int INF=1008611;
    void init()
    {
        int i,j;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&p[i][j]);
                if(p[i][j]==0)
                    p[i][j]=INF;//不连通的点值路径值为inf
            }
            vis[i]=0;//判断是否遍历该节点的数组
            path[i]=-1;//前继节点初始为-1
        }
    }
    void dj()
    {
        int i,j,k,minn,key;
        for(i=1;i<=n;i++)
        {
            dis[i]=INF;//初始化距离
        }
        dis[1]=0;
        for(i=1;i<=n;i++)
        {
            minn=INF;
            for(j=1;j<=n;j++)//贪心查找一个没有遍历过的距离最小的节点
            {
                if(!vis[j]&&minn>dis[j])
                {
                    minn=dis[j];
                    key=j;
                }
            }
           vis[key]=1;//标记
            for(j=1;j<=n;j++)
            {
                if(minn+p[key][j]<dis[j])//对该节点进行松弛操作
                {
                    path[j]=key;//记录路径
                    dis[j]=minn+p[key][j];
                }
            }
        }
    }
    void print()
    {
        int i=n,j;
        stack<int>q;
        while(path[i]!=-1)//用栈来实现路径还原
        {
            q.push(i);
            i=path[i];
        }
        q.push(i);
        while(!q.empty())
        {
            printf("%d",q.top());
            q.pop();
            if(!q.empty())
                printf(" ");
        }
        printf("\n");
    }
    int main()
    {
        int i,j;
        while(scanf("%d",&n)!=EOF)
        {
            init();
            dj();
            printf("minlong=%d\n",dis[n]);
            print();
        }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1868&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1868&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1868&soj=0