graphlib icon indicating copy to clipboard operation
graphlib copied to clipboard

Bug Report:Get wrong answer when running dijkstra in an undirected graph

Open OceanPresentChao opened this issue 3 years ago • 0 comments

Description

A clear and concise description of what the bug is that If you build an undirected graph and set edge between two nodes for only one time,you will get wrong answer when running dijkstra.

test("test Dijkstra in undirected graph", function () {
    const p = new graphlib.Graph({
        directed: false
    })
    p.setEdge("a", "b", 4);
    p.setEdge("a", "d", 2);
    p.setEdge("b", "d", 1);
    p.setEdge("c", "d", 1);
    p.setEdge("d", "e", 7);
    p.setEdge("e", "c", 3);
    p.setEdge("c", "b", 4);
    expect(graphlib.alg.dijkstra(p, "a", (e) => p.edge(e))).toBe({
        a: { distance: 0 },
        b: { distance: 3, predecessor: "d" },
        c: { distance: 3, predecessor: "d" },
        d: { distance: 2, predecessor: "a" },
        e: { distance: 6, predecessor: "c" },
    })
})

But we will get:

Object {
        "a": Object {
          "distance": 0,
        },
        "b": Object {
    -     "distance": 3,
    -     "predecessor": "d",
    +     "distance": 4,
    +     "predecessor": "a",
        },
        "c": Object {
    -     "distance": 3,
    -     "predecessor": "d",
    +     "distance": 8,
    +     "predecessor": "b",
        },
        "d": Object {
          "distance": 2,
          "predecessor": "a",
        },
        "e": Object {
    -     "distance": 6,
    -     "predecessor": "c",
    +     "distance": 9,
    +     "predecessor": "d",
        },
      }

Why and How to resolve it

The reason is that althrough we set "directed = false" in config,no special handling is done either when creating edges or when running the Dijkstra.So the atrribute "directed" extractly does nothing. QWQ

Therefore the solution is that we should set two edge between the nodes by ourselves.

OceanPresentChao avatar Apr 16 '22 04:04 OceanPresentChao