dijkstra.adoc

Dijkstra’s Algorithm

of this graph package by exploring details of the example program in the documentation. View the package documentation and find the example under LabeledAdjacencyList.DijkstraPath Here’s the code reproduced:

// arcs are directed right:
//          (wt: 11)
//       --------------6----
//      /             /     \
//     /             /(2)    \(9)
//    /     (9)     /         \
//   1-------------3----       5
//    \           /     \     /
//     \     (10)/   (11)\   /(7)
//   (7)\       /         \ /
//       ------2-----------4
//                 (15)
g := graph.LabeledAdjacencyList{
    1: {{To: 2, Label: 7}, {To: 3, Label: 9}, {To: 6, Label: 11}},
    2: {{To: 3, Label: 10}, {To: 4, Label: 15}},
    3: {{To: 4, Label: 11}, {To: 6, Label: 2}},
    4: {{To: 5, Label: 7}},
    6: {{To: 5, Label: 9}},
}
w := func(label graph.LI) float64 { return float64(label) }
p, d := g.DijkstraPath(1, 5, w)
fmt.Println("Shortest path:", p)
fmt.Println("Path distance:", d)

The example graph is taken from the Wikipedia page Dijkstra’s algorithm but with some weights changed. This tutorial will not cover the way the algorithm works. For that the Wikipedia page gives a good introduction.

The graph literal

That’s the construction graph.LabeledAdjacencyList{…​ To understand it, read the documentation on LabeledAdjacencyList and chase down the type definitions,

type LabeledAdjacencyList [][]Half
type Half struct {
    To    NI // node ID, usable as a slice index
    Label LI // half-arc ID for application data, often a weight
}
type NI int32
type LI int32

You can think of NI standing for "node int" or "node index", LI for "label int." Half is short for half-arc, half because the struct does not include the "from" node, but see that it’s just a struct of two integers. LabeledAdjacencyList then is a slice of slices of these structs. That’s it — the graph representation is fundamentally just a bunch of integers. This implements an adjacency list representation.

Is the : syntax strange to you? Review the Go language spec on composite literals and look for "KeyedElement." These are mostly used in map literals but can be very convenient for slice literals as well. Here the "KeyedElement" is our "from node." The line 3: {{To: 4, Label: 11}, {To: 6, Label: 2}}, represents two arcs in our graph, one going from node 3 to node 4 and another going from node 3 to node 6.

The weight function

"Weighted graphs" are kind of a thing and many graph libraries have data structures that directly represent weights. This graph package though abstracts them a bit. None of type definitions shown above directly define a weight. Instead, Half defines a "label" that can be used to index or encode arbitrary information. Dijkstra’s algorithm needs weights though, so the function signature for DijkstraPath has a WeightFunc argument. See these definitions in the doc, but Weight func is,

type WeightFunc func(label LI) (weight float64)

It’s just what we need to turn the label of the graph representation into the weight needed by Dijkstra’s algorithm. You, as programmer, write the weight function according to however weights are stored. This could involve a table lookup of some sort but in the simplest cases you can just store the weight directly as the label. That’s what we do here. All we need is a simple type conversion from the LI integer to float64:

w := func(label graph.LI) float64 { return float64(label) }

Method call

With a graph and a weight function, we’re ready to call DijkstraPath. We chose to find a shortest path starting at node 1 and ending at 5, and get back two interesting results, the path [1 6 5] and the distance 20.