用一道力扣题来完全掌握迪杰特斯拉算法（c++）-网络延迟时间-算法描述辅助记忆

网络延迟时间

题目链接
总结迪杰特斯拉写代码步骤（辅助记忆）：
1.把题目所给的条件存入邻接矩阵（c++中vector当数组使用），直接vector<vector> g(n, vector(n, inf));
ps 因为找到是最短路径，所以直接初始化为无穷大
2.初始化dist数组为无穷大，初始化源点；初始化used数组作为标记
3.开始算法的循环：第一层 执行n次，一个一个选入点并标记使用，更新最短路径dist
第二层 寻找未使用且dist最小的点（第一次会选择dist[k-1]即自身，完成初始化）
4.最后根据题目需求返回答案
看图辅助-图源：知乎-程序小哥爱读书

class Solution {
public:
    // 主函数，计算网络中从起点 k 到所有点的最短延迟时间
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int inf = INT_MAX / 2; // 定义无穷大为 INT_MAX / 2，防止整数溢出
        vector<vector<int>> g(n, vector<int>(n, inf)); // 邻接矩阵，存储节点间的直接距离

        // 填充邻接矩阵
        for (auto& t : times) {
        //此处使用引用可以省内存，不用每次都初始化一个新的
            int x = t[0] - 1, y = t[1] - 1; // 0-based index，输入通常为 1-based
            g[x][y] = t[2]; // t[2] 是从节点 x 到节点 y 的直接时间
        }

        vector<int> dist(n, inf); // dist 数组，存储从源点 k 到每个点的最短路径长度
        dist[k - 1] = 0; // 源点到自身的最短路径为 0
        vector<int> used(n); // 标记数组，用来标记某个节点的最短路径是否已经确定

        // 主循环，执行 n 次以确保每个节点的最短路径都被找到
        for (int i = 0; i < n; ++i) {
            int x = -1;
            // 寻找未使用的且 dist 最小的节点
            for (int y = 0; y < n; ++y) {
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }
            used[x] = true; // 标记节点 x 的最短路径已确定

            // 更新所有节点的最短路径
            for (int y = 0; y < n; ++y) {
                dist[y] = min(dist[y], dist[x] + g[x][y]); // 利用节点 x 更新其他节点的最短路径
            }
        }

        // 找到最长的最短路径，即网络延迟时间
        int ans = *max_element(dist.begin(), dist.end());
        return ans == inf ? -1 : ans; // 如果最长的最短路径为无穷大，说明有节点不可达，返回 -1
    }
};

原文地址：https://blog.csdn.net/Winnie12138_/article/details/140545562

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！