smallfang

Dijkstra算法笔记
祝六一快乐!开学快乐。不出意外,该篇文章应该于2020.06.01日发布。概述Dijkstra,一种最短路算法。时...
扫描右侧二维码阅读全文
01
2020/06

Dijkstra算法笔记

祝六一快乐!开学快乐。不出意外,该篇文章应该于2020.06.01日发布。

概述

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;
}

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

Last modification:August 10th, 2020 at 08:55 pm
End.

3 comments

  1. smallfang

    OωO

  2. wyy

    应该配一些图,效果会好些qwq

    1. smallfang
      @wyy

      好的,抽时间。

Leave a Comment