Yen's algorithm for the 3rd (and) subsequent shortest paths (k-shortest paths problem)

Question

So I understand how Yen's algorithm works for the 2nd shortest but not any subsequent iterations. In the third Iteration do you remove one unique pair of edges at a time (one from from the second 2nd shortest path, one the 1st shortest path)?

Here is my network:

    'MCO': {'ATL': 1.02, 'MIA': 0.63},
    'ATL': {'MCO': 1.07, 'DFW': 1.87},
    'DFW': {'MIA': 2.65, 'ATL': 1.63, 'DEN': 1.60},
    'DEN': {'LAS': 1.42, 'ORD': 2.08, 'DFW': 1.47},
    'LAS': {'DEN': 1.50, 'LAX': 0.71},
    'LAX': {'JFK': 5.43, 'ORD': 3.83, 'LAS': 0.75,},
    'ORD': {'CLT': 1.40, 'JFK': 1.67, 'LAX': 3.50},
    'MIA': {'DFW': 2.65, 'MCO': 0.67, 'JFK': 2.38},
    'CLT': {'ORD': 1.57,},
    'JFK': {'MIA': 2.53, 'ORD': 2.00, 'LAX': 4.85},

The first shortest path was found: MIA -> DFW -> DEN -> LAS

The second shortest path was found: MIA -> MCO -> ATL -> DFW -> DEN -> LAS

Now for the third iteration if I only remove MIA -> MCO or MCO -> ATL or ATL -> DFW , the first shortest path will be found again. Does that mean I have to run Dijkstra's algorithm on every unique pair of edges, i.e. 15 times?

Answer 1

the first shortest path will be found again.

Since you have forgotten to post your code, we can only guess at where your bug lies.

My best guess is that you have failed to correctly implement the line of psuedo code

        if (totalPath not in B):
            B.append(totalPath);

B is the set of potential shortest paths ( don't you love people who use meaningless variable names? ). The if statement prevents paths that have been 'found again' from being stored.

Since you haven't posted your code, here is my C++ implementation of Yen's algorithm

       static void combine_yen(
            std::pair<std::vector<int>, double> &spur,
            const std::pair<std::vector<int>, double> &prev,
            int rootlength,
            const sGraphData &gd         )
        {
            spur.first.insert(
                spur.first.begin(),
                prev.first.begin(), prev.first.begin() + rootlength - 1);
            spur.second = 0;
            for (int v = 1; v < spur.first.size(); v++)
                spur.second += gd.edgeWeight[gd.g.find(
                    spur.first[v - 1], spur.first[v])];
        }
        static bool isNewPath_yen(
            const std::pair<std::vector<int>, double> &test,
            const std::vector<std::pair<std::vector<int>, double>> &vShortestPaths)
        {
            return (
                std::find_if(
                    vShortestPaths.begin(), vShortestPaths.end(),
                    [&](const std::pair<std::vector<int>, double> &p)
                    {
                        return std::equal(
                            p.first.begin(), p.first.end(),
                            test.first.begin());
                    }) == vShortestPaths.end());
        }

        std::vector<std::pair<std::vector<int>, double>>
        shortestpathsYen(sGraphData &gd)
        {
            typedef std::vector<int> path_t;
            typedef std::pair<path_t, double> path_cost_t;
            std::vector<path_cost_t> vShortestPaths;
            std::vector<path_cost_t> vPotentialPaths;

            // Dijsktra gives the very shortest path
            vShortestPaths.push_back(path(gd));

            // loop looking for next shortest path
            while (vShortestPaths.size() < 3)
            {
                // initialize
                vPotentialPaths.clear();
                auto gdwork = gd;

                // loop over previously found shortest paths
                for (auto &foundPath : vShortestPaths)
                {
                    // loop over the previously found path
                    for (int rootlength = 1; rootlength < foundPath.first.size(); rootlength++)
                    {
                        // remove link from spur node used by previous path
                        gdwork.g.remove(
                            foundPath.first[rootlength - 1],
                            foundPath.first[rootlength]);

                        // find shortest path to destination ( spur path )
                        // without using the link
                        // dijsktra
                        gdwork.startName = gd.g.userName(foundPath.first[rootlength - 1]);
                        path_cost_t spurPath = path(gdwork);

                        // check spur path found
                        if (!spurPath.first.size())
                            continue;

                        // combine root and spur paths
                        combine_yen(
                            spurPath,
                            foundPath,
                            rootlength,
                            gd);

                        // check this is new path
                        if (isNewPath_yen(spurPath, vShortestPaths))
                            vPotentialPaths.push_back(spurPath);
                    }
                }

                // no more paths check
                if( ! vPotentialPaths.size() )
                    break;

                // Add shortest potential path to output
                vShortestPaths.push_back(
                    *std::min_element(
                        vPotentialPaths.begin(), vPotentialPaths.end(),
                        [](path_cost_t &a, path_cost_t &b)
                        {
                            return a.second < b.second;
                        }));
            }
            return vShortestPaths;
        }

Here is the adjacency list for the Wikipedia example

format shortestpaths
g 1
l c d 3
l d f 4
l c e 2
l d e 1
l e f 2
l e g 3
l f g 2
l g h 2
l f h 2
s c
e h

Here is the output

c -> e -> f -> h ->  cost 5.000000
c -> e -> g -> h ->  cost 7.000000
c -> d -> f -> h ->  cost 8.000000

Here is the adjacency list for the your example

format shortestpaths
g 1 1
l MCO ATL 1.02
l MCO MIA 0.63
l ATL MCO 1.07
l ATL DFW 1.87
l DFW MIA 2.65
l DFW ATL 1.63
l DFW DEN 1.60
l DEN LAS 1.42
l DEN ORD 2.08
l DEN DFW 1.47
1 LAX JFK 5.43
l LAX ORD 3.83
l LAX LAS 0.75
l ORD CLT 1.40
l ORD JFK 1.67
l ORD LAX 3.50
l MIA DFW 2.65
l MIA MCO 0.67
l MIA JFK 2.38
l CLT ORD 1.57
l JFK MIA 2.53
l JFK ORD 2.00
l JFK LAX 4.85
s MIA
e LAS

which outputs

MIA -> JFK -> LAX -> LAS ->  cost 4.550000
MIA -> JFK -> ORD -> LAX -> LAS ->  cost 5.530000
MIA -> DFW -> DEN -> LAS ->  cost 5.600000

The complete application is at https://github.com/JamesBremner/PathFinder and the user docs are at https://github.com/JamesBremner/PathFinder/wiki/Shortest-Paths