内容纲要

1.例题

本文以HDU2544为例:
file

  • 题目大意
    给出一个带权无向图,求其从起点到终点的最短路径。

    2.Dijkstra算法

  • 算法思路
    Dijkstra算法算一种贪心算法,通过不断选择中间点找出起点到各个点的最短路(这个操作被称为松弛)。该算法常用于求单源图的最短路,具体见伪代码。
  • 伪代码
    Dijkstra(){
    取邻接表起点行作为最短路记录数组;
    标记起点为已访问;
    以下操作循环次数为点的个数{
        找出最短路数组中未被访问的对应值最小的点并记录值为最小值,点位松弛点;
        标记最小值点为已访问;
        对所有最短路数组中的点{
            当前值与精工松弛点路径值中的较小值为新的最短路径值;
        }
    }
    }
  • 实现(HDU2544)

    #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<sstream>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<map>
    #include<set>
    #include<stack>
    #include<list>
    #include<queue>
    #include<ctime>
    #include<bitset>
    #include<cmath>
    #define eps 1e-6
    #define INF 0x3f3f3f3f
    #define PI acos(-1.0)
    #define M 1000000007
    using namespace std;
    typedef long long LL;
    const int maxn = 105;
    int adj[maxn][maxn];
    int dis[maxn];
    bool vis[maxn];
    void init(int n)
    {
    memset(vis,false,sizeof(vis));
    memset(adj,INF,sizeof(adj));
    memset(dis,INF,sizeof(dis));
    for(int i = 1;i <= n;++i)
        adj[i][i] = 0;
    }
    int dijkstra(int n)
    {
    int minn,tmp; //最短路径值与松弛点
    for(int i = 1;i <= n;++i)
        dis[i] = adj[1][i];
    vis[1] = true;
    for(int i = 1;i <= n;++i)
    {
        minn = INF;
        for(int j = 1;j <= n;++j)
            if(!vis[j] && minn > dis[j])
            {
                tmp = j;
                minn = dis[j];
            }
        if(minn == INF)
            break;
        vis[tmp] = true;
        for(int j = 1;j <= n;++j)
            dis[j] = min(dis[j],dis[tmp] + adj[tmp][j]);
    }
    return dis[n];
    }
    int main()
    {
    int n,m;
    while(~scanf("%d%d", &n, &m) && n && m)
    {
        init(n);
        int st,ed,l;
        for(int i = 1;i <= m;++i)
        {
            scanf("%d%d%d", &st, &ed, &l);
            adj[st][ed] = l; //注意本体是无向图,要使邻接表对称
            adj[ed][st] = l;
        }
        int ans = dijkstra(n);
        printf("%d\n", ans);
    }
    
    return 0;
    }

    3.Floyd算法

  • 算法思路
    个人认为,Floyd算法是一种dp算法,遍历每个点作为中间点的情况下另外每两个点间的路径,不断取最小值。这个过程过于简单,但是很暴力,时间复杂度高达O(n^3),通常用于求多源最短路。由于过程过于简单,故本文不给伪代码。
  • 实现(HDU2544)

    #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<sstream>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<map>
    #include<set>
    #include<stack>
    #include<list>
    #include<queue>
    #include<ctime>
    #include<bitset>
    #include<cmath>
    #define eps 1e-6
    #define INF 0x3f3f3f3f
    #define PI acos(-1.0)
    #define M 1000000007
    using namespace std;
    typedef long long LL;
    const int maxn = 105;
    int dp[maxn][maxn];
    int floyd(int n)
    {
    for(int tran = 1;tran < n;++tran) //遍历中转点
        for(int i = 1;i <= n;++i)
            for(int j = 1;j <= n;++j)
                dp[i][j] = min(dp[i][j],dp[i][tran] + dp[tran][j]); // i到j的最短路
                   return dp[1][n];
    }
    int main()
    {
    int n,m;
    while(~scanf("%d%d", &n, &m) && n && m)
    {
        int st,ed,l;
        memset(dp,INF,sizeof(dp));
        for(int i = 1;i <= n;++i)
            dp[i][i] = 0;
        for(int i = 1;i <= m;++i)
        {
            scanf("%d%d%d", &st, &ed, &l);
            dp[st][ed] = l;
            dp[ed][st] = l;
        }
        int ans = floyd(n);
        printf("%d\n", ans);
    }
    
    return 0;
    }

说明:最短路算法还有SPFA算法和Bellman_Ford算法,教材中没有做要求,本文就不写了。(其实是我忘了)(蔡得真实)考完后找时间再写。

总提纲:《数据结构》期末复习提纲小结

发表评论

电子邮件地址不会被公开。 必填项已用*标注