C++U6-02-最短路算法1-dijkstra迪杰斯特拉最短路径

小虾同学 / 2024-01-15 / 原文

学习目标

最短路径的基本概念

练习1

最短路的定义

本节课迪杰斯特拉dijkstra最短路算法

算法流程：

以下是 Dijkstra 最短路径算法的逐步计算松弛的过程：

初始化起始节点的距离为0，其他节点的距离为无穷大。
选择当前距离最小且未被访问的节点作为当前节点。
遍历当前节点的所有邻居节点：
- 计算通过当前节点到达邻居节点的距离（当前节点距离加上边的权重）。
- 如果计算得到的距离小于邻居节点的当前距离，则更新邻居节点的距离为新的距离。
标记当前节点为已访问的节点。
重复步骤2和步骤3，直到所有节点都被标记为已访问。
输出最短路径。

这个过程中，我们从起始节点开始，每次选择一个当前距离最小且未被访问的节点进行松弛操作。通过不断更新节点的距离值，最终可以找到起始节点到其他节点的最短路径。

练习1

练习2

练习

[单源最短路径1]

#include<iostream>
using namespace std;

const int maxn = 1005;
int e[maxn][maxn],dis[maxn],vis[maxn];   // 图的邻接矩阵，e[u][v]表示节点u到节点v的边权值
void dij(int n, int s) {
    for(int i = 0; i <= n; i++)// 初始化距离数组
        dis[i] = 1e9;  // 初始时将所有节点的最短路径估计值设为无穷大
    dis[s] = 0;       // 起点到自身的最短路径为0
    for(int i = 1; i <= n; i++) { // 循环更新最短路径
        int u = 0;  
        for(int j = 1; j <= n; j++)// 选择未访问的节点中距离起点最近的节点
            if(!vis[j] && dis[j] < dis[u]) u = j;  // !vis[j]是标记那些点做过起点了  //第一次没有任何一个距离要与dis[u] 因为是0 
        vis[u] = 1;  // 标记该节点为已访问
        for(int j = 1; j <= n; j++) {// 更新与选定节点相邻节点的最短路径估计值
            // 遍历与选定节点相邻的所有节点
            if(e[u][j]){   //判断的条件为点不是当前起点 
                cout<<u<<'_'<<j<<"  ";
                int v = j;  // 目标节点
                int w = e[u][j];  // 边权值
                if(dis[v] > dis[u] + w)// 尝试通过选定节点u更新到相邻节点v的最短路径估计值
                    dis[v] = dis[u] + w;  // 更新最短路径估计值
            }
        }
        cout<<endl;
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;  // 输入节点数、边数和起点
    // 输入图的边信息并初始化邻接矩阵
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // 如果已存在边，则取边权值的最小值，如果输入一样的那么只保留最短的
        int tmp = e[u][v] ? e[u][v] : 1e9;   //没输入的点初始的都是0；
    
        e[u][v] = min(tmp, w);
    }
    
    // 调用 Dijkstra 算法求解
    dij(n, s);
    
    // 输出最短路径长度
    for(int i = 1; i <= n; i++) {
        if(dis[i] != 1e9) cout << dis[i] << ' ';
        else cout << -1 << ' ';
    }
    
    return 0;
}