Shortest path with fewest edges: possible problem

#1

Looking at equals() and compareTo(), we take only distance and number of edges into consideration. We don’t look at the vertex id.

If we had a graph

a->b, 1
a->c, 1
a->d, 1

only one of b,c or d could be added to the set, because they are considered equal.

Or when we update the distance with a better distance:

      nodeSet.remove(v.vertex);
      v.vertex.pred = u;
      v.vertex.distanceWithFewestEdges
          = new DistanceWithFewestEdges(vDistance, vNumEdges);
      nodeSet.add(v.vertex);

we should encounter the same problem: add() would override some other vertex that has the same distance and hops.

I think we should also add vertex id to compareTo() and equals() in case both distance and hops are equal. Something like this:

    @Override
    public int compareTo(Vertex other) {
        if (this.distance != other.distance) {
            return Integer.compare(this.distance, other.distance);
        }

        if (this.hops != other.hops) {
            return Integer.compare(this.hops, other.hops);
        }

        return this.id.compareTo(other.id);
    }

    @Override
    public boolean equals(Object o) {
        Vertex other = (Vertex) o;

        return this == other || this.id.equals(other.id) && this.distance == other.distance && this.hops == other.hops;

    }
0 Likes
#2

Hey Duc,

Could you further explain what exactly the problem would be? For the given example (a->b, a->c, a->d), what is the start and end points here?

Personally I think equals probably need some modification as we want to add b, c, and d in the set.

0 Likes
#3

I wrote a test, corresponding to my example above, to show incorrect behavior:

    List<GraphVertex> G = new ArrayList<>();
    for (int i = 0; i < 4; ++i) {
        G.add(new GraphVertex());
        G.get(i).id = i;
    }

    // G[0] is the source node that connects to 8 other nodes.
    G.get(0).edges.add(new VertexWithDistance(G.get(1), 1)); // 0-1
    G.get(0).edges.add(new VertexWithDistance(G.get(2), 1)); // 0-2
    G.get(0).edges.add(new VertexWithDistance(G.get(3), 1)); // 0-3

    int s = 0;
    int t = 3;

If you output the sorted set on each iteration you will get:

Set state: [GraphVertex{id=0}]
Set state: [GraphVertex{id=1}]

The set should contain 3 vertices (1, 2 and 3), but instead it overrides already added vertex with id 1 each time, since distance and number of edges are the same.

Then it dequeues vertex with id 1 and the program stops, because equals() returns true when we compare it with the 3rd vertex.

To summarize there are two problems:

  • when we add a vertex to the set, we could override existing element even if it has another id
  • we could confuse some vertex the goal vertex, just because it has the same distance and number of edges
1 Like
#4

Hey Duc,

I tried to use your example to test the algorithm in Java but there is no error found. Would you mind to double-check this again?

For your example, it shows the path is “0 3”. The minimum distance is 1 and the number of edges is 1 between vertex 0 and vertex 3.

0 Likes
#5

Hi Tsung-Hsien,

yes, it shows the correct result. But as I wrote above vertex 3 was never added to the queue, only 0 and 1 were added. You can look it up in debugger or add some print statements.

If you want example that clearly reveals the bug, here it is:

    List<GraphVertex> G = new ArrayList<>();
    for (int i = 0; i <= 4; ++i) {
        G.add(new GraphVertex());
        G.get(i).id = i;
    }

    // G[0] is the source node that connects to 8 other nodes.
    G.get(0).edges.add(new VertexWithDistance(G.get(1), 1)); // 0-1
    G.get(0).edges.add(new VertexWithDistance(G.get(2), 1)); // 0-2
    G.get(0).edges.add(new VertexWithDistance(G.get(3), 1)); // 0-3

    G.get(2).edges.add(new VertexWithDistance(G.get(4), 1)); // 2-4

    int s = 0; // Source is G[0].
    int t = 4; // Destination is G[4].

Program output:

Min distance: 2147483647
Number of edges: 0
Number of edges: 0

This is all caused by equals() and compareTo() that ignore vertex ids. As a result vertices with different ids can be equal and we can override a vertex with another vertex in the queue.

I hope this clarifies my point.

1 Like
#6

Hey damluar,

Many thanks for your follow-up, and I have verified your case which proves the original implementation is flawed. So I just modified the compareTo and equals according to your suggestion.

Please keep up the good work, and again, thanks!

1 Like