时间戳

首页 > 解决方案 > 使用 Dijkstra 打印出第二最短路径的路径。和第二条第二条路径

c++ - 使用 Dijkstra 打印出第二最短路径的路径。和第二条第二条路径

问题描述

我正在尝试从 DIJKSTRA 中找到第二短的路径。假设我有以下顶点及其相互连接。a: c(19) f(34) i(58) l(94) o(108) p(104) b: a(46) d(47) e(36) j(82) p(88) q( 91) r(96) c: h(57) j(49) l(84) m(106) d: j(44) l(82) r(80) e: d(22) q(88) r( 79) t(93) f: b(53) d(19) s(93) g: h(36) j(102) o(64) p(65) h: a(60) d(56) f( 46) i(26) l(47) s(64) i: c(56) d(48) h(28) p(50) j: c(51) i(58) m(108) k: c( 68) g(96) i(51) j(34) l(55) s(77) t(77) l: b(76) c(84) e(69) g(64) j(73) k( 58) q(25) r(44) t(36) m: f(93) i(63) n: h(61) i(64) l(40) p(28) q(29) o: d( 95) e(84) k(71) q(16) p:

这是我如何找到最短路径和第二最短路径的代码。

for (int count= 0; count < V-1; count++)
{
    int u = minDis(dist, sptSet);
    sptSet[u] = true;

    for (int v = 0; v < V; v++)
    {
        if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
        {
            secDist[v] = dist[v];
            path[v] = u;
            dist[v] = dist[u] + graph[u][v];
            countVertices++;
        }
        else if(!sptSet[v] && graph[u][v] && dist[u] != INT_MAX &&        dist[u] + graph[u][v] < secDist[v])
        {
            secDist[v] = dist[u] + graph[u][v];
            secCountVertices++;
        }
    }
}

我得到了第二最短路径的正确距离和访问的节点总数，即 130 长度和路径（alt），我也得到了第二最短路径的长度，即 131，但我不知道如何打印出来第二最短路径。提前致谢！！

标签： c++

解决方案

我认为本教程将为您指明正确的方向，因为“printSolution()”似乎打印出了路径

推荐阅读