2020.02.11

本文主要是介绍2020.02.11，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

今天学习了djs算法，大概总结一下。

这个算法是求单源最短路径的。下面我就把模板和思路给给出来，一目了然。

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f; //无穷大,不邻接就是无穷大
int G[N][N], dis[N];        // G为邻接矩阵,dis为单源到i的权值
int p[N];                   //记录前驱
bool book[N];               //判断是否已经加入集合,集合表示已经更新过的结点
int n;
void dijkstra(int u, int n) // u是源点，源点到各个顶点的最短路径,n是定点数
{
    for (int i = 1; i <= N; i++) //初始化
    {
        dis[i] = G[u][i];
        book[i] = 0;
        /*
        if (dis[i] == INF) //如果等于INF，表示u无法到达这个顶点,则前驱为-1
            p[i] = -1;
        else
            p[i] = u;
            */
    }
    dis[u] = 0;                 // u到u的权值为0
    book[u] = 1;                //表示u已经更新过
    for (int i = 1; i < n; i++) //找最小并且更新dis
    {
        // printf("=============\n");
        int min = INF, t = u;
        for (int j = 1; j <= n; j++)
            if (!book[j] && dis[j] < min) //如果j没有更新过且是邻接
            {
                min = dis[j];
                t = j;
            }
        if (t == u) //优化
            return;
        book[t] = 1;
        // printf("t:%d\n", t);
        for (int j = 1; j <= n; j++)
        {
            if (!book[j] && dis[j] > dis[t] + G[t][j]) //如果某个顶点是同时和u和t邻接的，则更新dis[j]的值
            {
                // printf("dis[j]:%d\n", dis[j]);
                dis[j] = dis[t] + G[t][j];
                // p[j] = t; //更改j的前驱为t
                //  printf("dis[j]:%d\n", dis[j]);
            }
        }
    }
}
int main()
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            G[i][j] = INF;
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
        for (int j = i + 1; j <= n; j++)
            cin >> G[i][j];
    dijkstra(1, n);
    cout << dis[3] << endl;
}

这篇关于2020.02.11的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！