关于dijastra程序里个别段的疑惑

精

奖

官

339 产品版区：S7-1500

文档类型：问题类别：产品选型问题类别：产品使用问题类别：故障诊断

REGION Algorithm init// Dijkstra 算法初始化
        FOR #tempI := 0 TO #vertexNum-1 DO
            //S初始为空集
            #statSs[#tempI] := FALSE;//表示初始时没有顶点被访问
            #tempRefDs^[#tempI]:=#tempRefAdjaMatrix^[0,#tempI];//将d数组初始化为从源点（顶点0）到各顶点的直接距离
            IF  #tempRefDs^[#tempI] < "INF" THEN//如果距离小于INF（无穷大），
                #tempRefPaths^[#tempI] := 0;//则路径设置为0（源点），
            ELSE
                #tempRefPaths^[#tempI] := -1;//否则路径设为-1（不可达）
            END_IF;
        END_FOR;
        #statSs[0] := TRUE;//然后将源点0加入S集合。
    END_REGION

    REGION Dijkstra Algorithm
        // Dijkstra最短路径算法

    FOR #tempI :=1 TO #vertexNum-1 DO

        #tempMin := "INF";
        //在D中选择当前的最短路径
        FOR #tempJ := 1 TO #vertexNum-1 DO
            // 选择一条当前的最短路径
              IF (NOT #statSs[#tempJ]) AND (#tempRefDs^[#tempJ]<#tempMin) THEN
                  #tempMin := #tempRefDs^[#tempJ];
                  #tempV := #tempJ;
              END_IF;
          END_FOR;
          //将找到的顶点加入到S集合
          #statSs[#tempV] := true;

          //借助新找到的最短路径顶点V 更新从v0出发到集合V上所有顶点的最短路径长度
          FOR #tempK := 1 TO #vertexNum-1 DO
            #tempD := #tempRefDs^[#tempV] + #tempRefAdjaMatrix^[#tempV, #tempK];
            IF (NOT #statSs[#tempK]) AND (#tempD < #tempRefDs^[#tempK]) THEN
                #tempRefDs^[#tempK] := #tempD;
                #tempRefPaths^[#tempK] := #tempV;
            END_IF;

           END_FOR;

    END_FOR;

    END_REGION

    ELSE
        #error := TRUE;
        #status := #INPUT_PARA_ILLEGAL;

    END_IF;
END_IF;
#statExcuteOld := #excute;
*********************************************************************************************************************
在最短路径算法中
”FOR #tempI :=1 TO #vertexNum-1 DO“跟
   FOR #tempJ := 1 TO #vertexNum-1 DO
            // 选择一条当前的最短路径
              IF (NOT #statSs[#tempJ]) AND (#tempRefDs^[#tempJ]<#tempMin) THEN
                  #tempMin := #tempRefDs^[#tempJ];
                  #tempV := #tempJ;
              END_IF;
          END_FOR;
看上去毫无关联啊，不参与寻找最短路径，也不参与更新tempi
这是什么情况》？它起到了什么作用

问题补充：

扫码小程序：

一键登录查看全部问答

BH9BXR-1 资深学长

被采纳率 27.27%

问题为何被关闭

分享

手机扫码追踪该问题，
觉得实用，立即去分享！

点击复制链接
举报

去论坛讨论

虽然外层循环 #tempI 和内层循环 #tempJ 在代码中看起来没有直接的关联，但它们在逻辑上是紧密相连的。外层循环负责逐步构建最短路径集合 S，而内层循环负责在每次外层循环迭代中找到当前最短路径的顶点。这种结构是 Dijkstra 算法的标准实现方式，确保了算法能够逐步找到从源点到所有顶点的最短路径。
1. 外层循环 FOR #tempI := 1 TO #vertexNum-1 DO 的作用
这个外层循环的目的是逐步构建最短路径集合 S，并逐步更新从源点 v0 到所有其他顶点的最短路径。每次循环迭代都会找到一个尚未加入集合 S 的顶点，将其加入 S，并更新从源点到其他顶点的最短路径。
1)循环次数：#vertexNum-1 次，因为源点已经初始化加入集合 S，所以只需要再选择 n?1 个顶点。
2)每次迭代的目标：找到一个尚未加入集合 S 的顶点，使其成为当前最短路径的顶点，并将其加入集合 S。
2. 内层循环 FOR #tempJ := 1 TO #vertexNum-1 DO 的作用
这个内层循环的作用是从尚未加入集合 S 的顶点中，找到当前最短路径的顶点。具体步骤如下：
1)初始化：#tempMin 被设置为无穷大（"INF"），用于记录当前找到的最短路径长度。
2)遍历所有顶点：从 1 到 n?1 遍历所有顶点，检查每个顶点是否尚未加入集合 S（NOT #statSs[#tempJ]），并且其当前路径长度是否小于当前已知的最短路径长度（#tempRefDs^[#tempJ] < #tempMin）。
3)更新最短路径：如果找到一个更短的路径，则更新 #tempMin 和 #tempV，其中 #tempV 记录当前最短路径的顶点。
3. 两层循环的关联
        虽然外层循环 #tempI 和内层循环 #tempJ 在代码中看起来没有直接的关联，但它们在逻辑上是紧密相连的：
1)外层循环的每次迭代：都依赖于内层循环找到的最短路径顶点。内层循环找到的最短路径顶点 #tempV 会被外层循环用来更新集合 S 和路径长度。
2)内层循环的每次迭代：都是为了找到当前最短路径的顶点，为外层循环的下一步操作提供基础。
4. 具体逻辑解释
1)外层循环：负责逐步构建最短路径集合 S，并更新从源点到所有顶点的最短路径。
2)内层循环：在每次外层循环迭代中，负责找到当前最短路径的顶点。
5. 代码逻辑的详细解释
FOR #tempI := 1 TO #vertexNum-1 DO
    #tempMin := "INF";
    // 在 D 中选择当前的最短路径
    FOR #tempJ := 1 TO #vertexNum-1 DO
        // 选择一条当前的最短路径
        IF (NOT #statSs[#tempJ]) AND (#tempRefDs^[#tempJ] < #tempMin) THEN
            #tempMin := #tempRefDs^[#tempJ];
            #tempV := #tempJ;
        END_IF;
    END_FOR;
    // 将找到的顶点加入到 S 集合
    #statSs[#tempV] := TRUE;
    // 借助新找到的最短路径顶点 V 更新从 v0 出发到集合 V 上所有顶点的最短路径长度
    FOR #tempK := 1 TO #vertexNum-1 DO
        #tempD := #tempRefDs^[#tempV] + #tempRefAdjaMatrix^[#tempV, #tempK];
        IF (NOT #statSs[#tempK]) AND (#tempD < #tempRefDs^[#tempK]) THEN
            #tempRefDs^[#tempK] := #tempD;
            #tempRefPaths^[#tempK] := #tempV;
        END_IF;
    END_FOR;
END_FOR;
5总结：
1）外层循环：每次迭代都会找到一个最短路径的顶点，并将其加入集合 S。
2）内层循环：每次外层循环迭代中，找到当前最短路径的顶点。
3）更新路径：找到最短路径的顶点后，更新从源点到其他顶点的最短路径。