本篇文章即将维护

概述

Dijkstra，一种最短路算法。时间复杂度为n^2.

算法实现

利用贪心进行实现。

实现过程

首先设置起点dis值为0，其次寻找n次，每次找到dis数组里最小的。然后通过给定的权值表更新其他值。以此类推
最后的dis表就是每个点之间距离最短的了。
Code:

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int n, m, k, s, e;
int dis[1001];
int g[1001][1001];
bool gt[1001];

int main()
{
  
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++ )
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        g[x][y] = z;
        g[y][x] = z;
    }
    memset(dis, 127, sizeof(dis));
    scanf("%d%d", &s, &e);
    dis[s] = 0;
    for(int i = 1 ; i <= n; i ++ )
    {
        int in = 2147483647;
        int w = 0;
        for(int j = 1; j <= n; j ++ )
        {
            if(gt[j] == false && dis[j] < in)
            {
                in = dis[j];
                w = j;
            }
        }
        gt[w] = true;
        for(int j = 1; j <= n; j ++ )
        {
            if(g[w][j] != 0 && g[w][j] + dis[w] < dis[j])
            {
                dis[j] = g[w][j] + dis[w];
            }
        }
    }
    printf("%d", dis[e]);
    return 0;
}

最近博客质量太水了...
我决定要提高！

最后修改：2022 年 11 月 26 日
© 允许规范转载
End.