dijkstra gives wrong result

[sigs]

Reproduction:

const { Graph, alg: { dijkstra } } = require("graphlib")

function ring(size, prefix) {
    if (size < 1) { return [] }
    const nodes = [prefix + "0"]
    const edges = []
    for (let i = 1; i < size; i++) {
        nodes.push(prefix + i)
        edges.push([nodes[i - 1], nodes[i]])
    }
    edges.push([nodes[size - 1], nodes[0]])
    return { nodes, edges }
}

function graph(obj, g) {
    if (obj.nodes) {
        obj.nodes.forEach(n => g.setNode(n))
    }
    if (obj.edges) {
        obj.edges.forEach(e => g.setEdge(e[0], e[1]))
    }
    return g
}

const r = ring(5, "ring_", 1)
const g = graph(r, new Graph({directed: false}))
const d = dijkstra(g, "ring_0", () => 1)
console.log(JSON.stringify(r))
console.log(JSON.stringify(d))

Prints:

{"nodes":["ring_0","ring_1","ring_2","ring_3","ring_4"],"edges":[["ring_0","ring_1"],["ring_1","ring_2"],["ring_2","ring_3"],["ring_3","ring_4"],["ring_4","ring_0"]]}
{"ring_0":{"distance":0},"ring_1":{"distance":1,"predecessor":"ring_0"},"ring_2":{"distance":2,"predecessor":"ring_1"},"ring_3":{"distance":3,"predecessor":"ring_2"},"ring_4":{"distance":1,"predecessor":"ring_0"}}

Expected:

• d.ring_3.distance == 2
• d.ring_3.predecessor == 'ring_4'

Actual:

• d.ring_3.distance == 3
• d.ring_3.predecessor == 'ring_2'

Seems the algorithm takes the "wrong" route for some reason. Could be user error, please enlighten me :)

[DLewis01]

I think the problem is ring_0, ring_1. I don't know why, but I think it messes up when you have a mix of letters and numbers in the nodes.

Try it with ring_a, ring_b, etc