Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
OceanPresentChao opened this issue Apr 16, 2022 · 0 comments

Comments

@OceanPresentChao
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant