18.9 Shortest Path with fewer edges comparator bug

#1

There seems to be a bug in the C++ solution of problem 18.9 Shortest path with fewer edges. The comparator considers two different vertices with same distance as identical. This will prevent addition of the new vertex in the node_set when its distance is same as some other vertex in the set. Eventually algorithm will not be able to explore paths through that vertex.

Here is simple test function that will not work with the solution given in the book:

int main() {
     GraphVertex a,b,c,d;
     a.id=1; b.id=2; c.id=3; d.id=4;
 
     a.edges.emplace_back(GraphVertex::VertexWithDistance{b,1});
     a.edges.emplace_back(GraphVertex::VertexWithDistance{c,1});
     c.edges.emplace_back(GraphVertex::VertexWithDistance{d,2});
 
     DijkstraShortestPath(&a, &d);
}

The solution would be comparing id as well in comparator when distance becomes equal. We can choose to put them in any order:

struct Comp {
    bool operator() (const GraphVertex* lhs, const GraphVertex* rhs) {
        return lhs->distance_with_fewest_edges.distance < rhs->distance_with_fewest_edges.distance
            || (lhs->distance_with_fewest_edges.distance == rhs->distance_with_fewest_edges.distance &&
                lhs->distance_with_fewest_edges.min_num_edges < rhs->distance_with_fewest_edges.min_num_edges)
        	|| (lhs->id < rhs->id);
    }
};

Am I missing anything?

0 Likes