概念

从图中的指定出发点，达到图中任意一点的最短距离，称为单源最短路

方法

迪杰斯特拉

将图分成两部分，一部分是已经访问，一部分是未访问

dp[i] 表示从起点到目标点 i 的最短距离

m[i][j] 表示从点 i 到点 j 的权重

初始化： 将 dp[i] 设置为从 1 到 i 的距离，将所有距离设置为无穷大

DP：找到未访问的点中距离最短的点 k，更新到剩下的所有点 j 的距离

dp[j] = min(dp[j], dp[k] + m[k][j])

笔记

时间复杂度

注意

通过斐波那契堆优化可以达到 的时间复杂度

提示

有向图和无向图都行

警告

迪杰斯特拉算法不能求带负权的单源最短路，并且是无环图

贝尔曼福特

SPFA

优先队列优化的 SPFA

题目

HDU 2544

http://acm.hdu.edu.cn/status.php?user=dyxinhun&pid=2544&status=5

用 迪杰斯特拉 算法

//
// Created by Administrator on 2021/10/18.
// 单源最短路 HDU 2544

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<cstring>

const int MAXV = 0x3f3f3f3f;
const int MAXN = 101;

int cost[MAXN][MAXN];

using namespace std;

void dijk(int n){
    int dp[MAXN];  // 到某个点的最短路径
    bool used[MAXN];  // 标记某个点是否走过

    // 初始化，到 i 的路径为1到i的距离
    for(int i = 1; i <= n; i++){
        dp[i] = cost[1][i];  //
        used[i] = false;
    }

    used[1] = true; // 从1开始出发

    int k; // 记录未访问的里面哪个最近

    for(int i = 2; i <= n; i++){

        // 找到未访问的里面离哪个最近
        int minv = MAXV;
        for(int j = 1; j <= n; j++){
            if(!used[j] && dp[j] < minv){
                minv = dp[j];
                k = j;
            }
        }

        used[k] = true; // 访问该节点

        for(int j = 1; j <= n; j++){
            if(!used[j] && dp[k] + cost[k][j] < dp[j]){
                dp[j] = dp[k] + cost[k][j];
            }
        }
    }
    printf("%d\n", dp[n]);
}

int main(){

    int n, m;
    while(scanf("%d %d", &n, &m) && (n || m)){
        memset(cost, 0x3f, sizeof(cost));
        int a, b, c;

        for(int k = 0; k < m; k++){
            scanf("%d %d %d", &a, &b, &c);
            cost[a][b] = cost[b][a] = c;
        }
        dijk(n);
    }
    return 0;
}

参考链接：

OI-wiki (opens new window)