dijkstra

package module
v1.7.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 25, 2026 License: MIT Imports: 6 Imported by: 0

README

go-dijkstra

CI Go Reference Go Report Card

A small, dependency-free shortest-path library for Go — Dijkstra and goal-directed A* over a named directed graph — with one-way edges, dynamic vertex blocking, and optional X / Y / Heading metadata for spatial graphs (robot / AGV pathfinding on a 2D map).

Install

go get github.com/ultramcu/go-dijkstra

Requires Go 1.18 or newer. No third-party dependencies.

Quick example

package main

import (
    "fmt"

    dijkstra "github.com/ultramcu/go-dijkstra"
)

func main() {
    var g dijkstra.StGraph

    g.VertexAdd("A", 0, 0, 0,
        dijkstra.StEdge{ToVertexName: "B", Weight: 1, IsOneWay: true},
        dijkstra.StEdge{ToVertexName: "C", Weight: 5, IsOneWay: true},
    )
    g.VertexAdd("B", 1, 0, 0,
        dijkstra.StEdge{ToVertexName: "C", Weight: 2, IsOneWay: true},
    )
    g.VertexAdd("C", 2, 0, 0)

    ok, path := g.DijkstraSearch("A", "C")
    if !ok {
        fmt.Println("no path")
        return
    }
    for _, p := range path {
        fmt.Printf("%s (cost %.0f)\n", p.Name, p.Cost)
    }
    // A (cost 0)
    // B (cost 1)
    // C (cost 3)
}

Switching to A* is a drop-in — same arguments, same optimal result, but goal-directed: it uses the vertices' X / Y for a built-in straight-line (Euclidean) heuristic, so it explores far fewer vertices on large maps.

ok, path := g.AStarSearch("A", "C")          // built-in Euclidean heuristic

// ...or supply your own heuristic (nil == Euclidean; return 0 == Dijkstra):
manhattan := func(cx, cy, gx, gy float64) float64 {
    return math.Abs(cx-gx) + math.Abs(cy-gy)
}
ok, path = g.AStarSearchFunc("A", "C", manhattan)

Runnable examples

The example/ directory has small main programs you can run from the repo root:

go run ./example/dijkstra   # shortest path on a small map + dynamic blocking
go run ./example/astar      # A* on a grid; shows the heuristic pruning the search
go run ./example/compare    # Dijkstra vs A* timing and vertices-expanded table

There are also runnable godoc examples on pkg.go.dev (ExampleStGraph_DijkstraSearch, ExampleStGraph_AStarSearch, ExampleStGraph_VertexBLock).

Features

  • Directed graph with one-way edges supported via StEdge{IsOneWay: true}.
  • Dijkstra shortest path between any two named vertices. DijkstraSearch returns an ordered slice of StPath nodes with cumulative cost on each entry.
  • A* goal-directed search — AStarSearch returns the same optimal path as DijkstraSearch but, guided by a heuristic, expands far fewer vertices on large maps. It uses a built-in straight-line (Euclidean) heuristic over each vertex's X/Y; supply your own with AStarSearchFunc (a heuristic that returns 0 reduces A* to Dijkstra).
  • Dynamic vertex blocking — mark a vertex as off-limits and the next search routes around it (it becomes unreachable). The blocked set is consulted on every search, so you can block/unblock at any time — handy for obstacles that appear and clear on a live map.
  • Dynamic graph editing — add or remove vertices and edges after the graph is built (VertexRemove, VertexAddEdge, VertexRemoveEdge). Removing a vertex also drops every edge into or out of it. Each search reflects the current graph.
  • Optional spatial metadata — every vertex has X, Y, Heading fields. Leave them at zero for non-spatial graphs, or use them with the bundled helpers (NearPoint, DistanceCMToVertex, Distance, DistanceCM).
  • Zero dependencies — pure standard library.

Performance

v1.7.2 ships a rewritten, integer-indexed search engine, and it is fast: roughly 2.5–3× quicker than the previous release while using about half the memory — and the same shortest paths, with zero API changes. Where the speed comes from:

  • Integer-indexed hot loop — vertex names are resolved to dense indices once per search; relaxation then runs over flat int-indexed slices with no per-edge map lookups and no string churn.
  • Cached CSR adjacency — a compressed integer adjacency is built once and reused across searches, rebuilt only when the graph's structure actually changes.
  • Reused buffers + O(1) reset — the priority queue and per-vertex scratch are reused between searches, and a generation counter invalidates stale state in O(1) instead of clearing every vertex.
  • Net result: a flat 7–9 allocations per search, regardless of graph size — and an O(1) name lookup + O(1) blocked-set test as before.

Measured on a 4-connected unit-weight grid (go test -bench=BenchmarkScale -benchmem, median of 6), this engine vs the previous (v1.7.1) one:

Search Vertices Before (v1.7.1) After (v1.7.2) Speed Memory
Dijkstra (full tree) 1,024 387 µs · 15 KB · 14 118 µs · 7.5 KB · 7 −70 % −50 %
Dijkstra (full tree) 10,000 4.47 ms · 64 KB · 18 1.77 ms · 32 KB · 9 −60 % −50 %
Dijkstra (full tree) 25,600 12.8 ms · 64 KB · 18 4.89 ms · 32 KB · 9 −62 % −50 %
A* (goal-directed) 10,000 319 µs · 23 KB · 15 114 µs · 7.5 KB · 7 −64 % −68 %
A* (goal-directed) 25,600 868 µs · 23 KB · 15 366 µs · 7.5 KB · 7 −58 % −68 %

That winning engine was picked by benchmarking five independently written candidates back-to-back and keeping the one that came out best on both axes — speed and memory. Reproduce on your machine with go test -bench=BenchmarkScale -benchmem (or go run ./example/compare).

A* vs Dijkstra. DijkstraSearch computes the full single-source tree; AStarSearch stops at the goal and prunes toward it. For a mid-range query A* expands far fewer vertices (81 vs Dijkstra's 1,024 on a 32×32 grid) and is several times faster on that query. For a corner-to-corner query — where the straight-line heuristic barely helps a 4-connected grid and the goal is the farthest vertex — A* matches Dijkstra (within ~5 %). Reach for A* on single source→goal queries with a heuristic suited to your metric (Euclidean for geometric maps; pass a Manhattan heuristic for 4-connected grids); keep DijkstraRun when you want every shortest path from one source.

API at a glance

Type Purpose
StGraph The graph; holds vertices, edges, and the blocked set.
StVertex One node; Name, X, Y, Heading, Edges, Weight, Visited, Parent, MaskSearch.
StEdge Outgoing edge: ToVertexName, Weight, IsOneWay.
StPath One node in a returned path: Name, X, Y, Heading, Cost.
StPriorityQueue Ascending-by-weight priority queue used by DijkstraRun and AStarSearch. Exported for reuse.
StStack LIFO stack of strings. Exported for reuse.
HeuristicFunc func(curX, curY, goalX, goalY float64) float64 — cost-to-goal estimate for A*.
Function / method Purpose
g.VertexAdd(name, x, y, heading, edges...) Add a vertex with outgoing edges.
g.VertexRemove(name) bool Remove a vertex plus every edge into/out of it; drops it from the blocked set.
g.VertexAddEdge(from, to, weight, isOneWay) bool Add an outgoing edge to an existing vertex.
g.VertexRemoveEdge(from, to) bool Remove a single edge.
g.VertexFind(name) int Slice index of a vertex, or -1.
g.VertexIsExist(name) bool Whether the vertex exists.
g.VertexBLockLoad([]string) / VertexBLock(name) / VertexBLockRemove(name) / VertexIsBLock(name) / VertexBLockClear() Manage the blocked set (see note below).
g.DijkstraSearch(from, to) (bool, []StPath) Find the shortest path.
g.AStarSearch(from, to) (bool, []StPath) Goal-directed shortest path using the built-in Euclidean heuristic.
g.AStarSearchFunc(from, to, h) (bool, []StPath) A* with a custom HeuristicFunc (nil = Euclidean; return 0 = Dijkstra).
EuclideanHeuristic(curX, curY, goalX, goalY) float64 The default straight-line A* heuristic.
g.DijkstraRun(from) bool Run only the relaxation pass; populates Weight / Parent / Visited on every reachable vertex. Useful when you want all shortest paths from a single source.
g.NearPoint(x, y) (string, float64) Vertex with (X, Y) closest to (x, y), returned with its distance in cm.
g.DistanceCMToVertex(x, y, name) (bool, float64) Distance in cm from (x, y) to a named vertex.
Distance(x1, y1, x2, y2) float64 Euclidean distance helper.
DistanceCM(x1, y1, x2, y2) float64 Same, scaled by 100.
g.Show(w io.Writer) / g.ShowDijkstra(w) Write the graph (or its post-search state) to any writer — no need to loop and print yourself. Print / PrintDijkstra are the os.Stdout shorthands.
g.ShowFunc(w, func(StVertex) string) Show with your own per-vertex formatter (nil = DefaultVertexLine).
PathString(path) string Render a returned path as "A -> B -> C (cost 6)".
g.Debug(true) Enable verbose logging on all subsequent operations.

Notes and limitations

  • Non-negative weights only. Dijkstra's algorithm requires non-negative edge weights. VertexAdd rejects (returns false) a vertex whose edges include any negative weight, rather than silently returning an incorrect shortest path later.
  • Dynamic blocking. The blocked set is consulted on every search, so VertexBLock / VertexBLockLoad / VertexBLockRemove / VertexBLockClear take effect on the next DijkstraSearch and may be called at any time (before or after VertexAdd). A blocked vertex is treated as unreachable; you can still route out of one when it is the search's start.
  • Goroutine-safe. Every StGraph method is safe to call from multiple goroutines. Internally a sync.RWMutex protects the graph: read methods take the read lock, mutations and searches take the write lock. Concurrent searches on the same graph therefore serialise (a search mutates per-vertex working state), but parallel reads of an idle graph run freely. For typical fleet workloads the serialised throughput is well above what one graph instance ever needs.
  • Sized for small-to-medium graphs. Vertex lookup and blocked-set membership are O(1), and the priority queue is an O(log n) binary heap. This is comfortable from tens up to tens of thousands of vertices. Plain Dijkstra explores outward in all directions; for large spatial graphs prefer the goal-directed AStarSearch, which uses the X / Y metadata to explore far less (see Performance).
  • Naming. The St prefix on exported types and the (bool, T) success-flag return convention are the author's intentional house style.

License

MIT — SPDX-License-Identifier: MIT.

Drop this module into any project (open or closed, commercial or otherwise). Just keep the copyright + permission notice with the source.

Documentation

Overview

Package dijkstra is a small, dependency-free shortest-path library for Go: Dijkstra and goal-directed A* search over a named directed graph.

It targets spatial pathfinding on small-to-medium maps -- robot / AGV navigation, game grids, road networks -- where vertices carry optional X / Y / Heading coordinates.

  • Dijkstra shortest path (DijkstraSearch) and full single-source trees (DijkstraRun).
  • A* goal-directed search (AStarSearch / AStarSearchFunc) with a built-in Euclidean heuristic or a caller-supplied HeuristicFunc.
  • One-way edges, dynamic vertex blocking, and runtime graph editing (add / remove vertices and edges) -- each search reflects the current graph.
  • A binary-heap priority queue and O(1) name lookups; zero third-party dependencies (Go 1.18+).

Exported types use an St prefix (StGraph, StVertex, StEdge, StPath) and methods return a (bool, T) success flag, kept consistent with the author's other Go code.

All exported StGraph methods are safe for concurrent use; internally a sync.RWMutex serialises mutations and searches while allowing parallel reads of an idle graph.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func DefaultVertexLine added in v1.7.1 

func DefaultVertexLine(v StVertex) string

DefaultVertexLine is the formatter Show and Print use when no custom one is supplied. It is exported so a ShowFunc callback can reuse or extend it.

func Distance 

func Distance(x1, y1, x2, y2 float64) float64

Distance returns the Euclidean distance between (x1, y1) and (x2, y2). The unit of the result matches the unit of the inputs.

func DistanceCM 

func DistanceCM(x1, y1, x2, y2 float64) float64

DistanceCM is Distance multiplied by 100, useful when the input coordinates are in metres and the caller wants centimetres.

func EuclideanHeuristic added in v1.7.0 

func EuclideanHeuristic(curX, curY, goalX, goalY float64) float64

EuclideanHeuristic is the default heuristic: the straight-line distance from the current vertex to the goal. It is the tightest admissible estimate when edge weights are Euclidean distances.

func PathString added in v1.7.1 

func PathString(path []StPath) string

PathString renders a path returned by DijkstraSearch / AStarSearch as "A -> B -> C (cost 6)", so callers don't have to loop over the slice just to print a result. An empty path returns "(no path)".

Types

type HeuristicFunc added in v1.7.0 

type HeuristicFunc func(curX, curY, goalX, goalY float64) float64

HeuristicFunc estimates the remaining cost from a vertex at (curX, curY) to the goal at (goalX, goalY). A* explores vertices in order of f = g + h, where g is the cost already spent to reach the vertex and h is this estimate.

For A* to return a provably shortest path the heuristic must be admissible (never overestimate the true remaining cost). The built-in EuclideanHeuristic is admissible -- and consistent -- whenever edge weights are real spatial distances between the vertices' (X, Y) coordinates, which is the common case for the geometric graphs this package targets (robot / AGV maps, road networks). If your edge weights mean something else (time, a penalty, ...), supply a heuristic in the same units that does not overestimate, or pass one that always returns 0 -- in which case A* degenerates to Dijkstra and is still correct.

type StEdge 

type StEdge struct {
	ToVertexName string
	Weight       float64

	IsOneWay bool
	// contains filtered or unexported fields
}

StEdge is a directed edge from the owning vertex to ToVertexName.

IsOneWay = true means the edge may only be traversed from the owning vertex to ToVertexName during search; the reverse direction will not be promoted to the shortest-path tree.

isShort is set internally by DijkstraRun; it is unexported and not part of the public contract.

type StGraph 

type StGraph struct {
	// contains filtered or unexported fields
}

StGraph is a directed graph supporting Dijkstra shortest-path search and optional vertex blocking. The zero value is a usable empty graph.

All exported methods are safe for concurrent use. Internally, methods named with a "Locked" suffix assume the caller already holds g.mu and are used by the search internals to avoid re-entrant locking.

func (*StGraph) AStarSearch added in v1.7.0 

func (g *StGraph) AStarSearch(fromVertex, toVertex string) (bool, []StPath)

AStarSearch finds the shortest path from fromVertex to toVertex using A* with the built-in straight-line (Euclidean) heuristic over the vertices' (X, Y) coordinates.

It returns the same result as DijkstraSearch -- ok plus a slice of StPath nodes ordered source-to-destination with cumulative Cost -- but, because the search is goal-directed, it usually expands far fewer vertices on large spatial graphs. The built-in heuristic assumes edge weights are spatial distances; see HeuristicFunc for when to supply your own via AStarSearchFunc.

Example

ExampleStGraph_AStarSearch finds the same shortest path as DijkstraSearch but goal-directed, using the built-in straight-line heuristic over the vertices' (X, Y) coordinates. 

package main

import (
	"fmt"

	dijkstra "github.com/ultramcu/go-dijkstra"
)

func main() {
	var g dijkstra.StGraph

	// Vertices on a line at x = 0,1,2,3. Edge weights equal the
	// straight-line distance, so the built-in heuristic is admissible.
	// A direct S->T hop exists but is slower than going via A, B.
	g.VertexAdd("S", 0, 0, 0,
		dijkstra.StEdge{ToVertexName: "A", Weight: 1, IsOneWay: true},
		dijkstra.StEdge{ToVertexName: "T", Weight: 5, IsOneWay: true},
	)
	g.VertexAdd("A", 1, 0, 0, dijkstra.StEdge{ToVertexName: "B", Weight: 1, IsOneWay: true})
	g.VertexAdd("B", 2, 0, 0, dijkstra.StEdge{ToVertexName: "T", Weight: 1, IsOneWay: true})
	g.VertexAdd("T", 3, 0, 0)

	ok, path := g.AStarSearch("S", "T")
	if !ok {
		fmt.Println("no path")
		return
	}
	for _, p := range path {
		fmt.Printf("%s (cost %.0f)\n", p.Name, p.Cost)
	}
}

Output:
S (cost 0)
A (cost 1)
B (cost 2)
T (cost 3)

func (*StGraph) AStarSearchFunc added in v1.7.0 

func (g *StGraph) AStarSearchFunc(fromVertex, toVertex string, h HeuristicFunc) (bool, []StPath)

AStarSearchFunc is AStarSearch with a caller-supplied heuristic. Passing nil uses EuclideanHeuristic. A heuristic that always returns 0 makes A* behave exactly like Dijkstra.

As with DijkstraSearch, this resets all per-vertex search state and holds the graph's mutex for the whole call, so concurrent searches on the same graph serialise (they stay race-free).

func (*StGraph) Debug 

func (g *StGraph) Debug(debugEn bool)

Debug toggles verbose printing during graph operations and search.

func (*StGraph) DijkstraInit 

func (g *StGraph) DijkstraInit()

DijkstraInit clears per-vertex Dijkstra state on every vertex (Visited, MaskSearch, Weight, Parent, and the per-edge isShort flag). Called automatically by DijkstraRun; the caller usually does not need to invoke it directly.

func (*StGraph) DijkstraRun 

func (g *StGraph) DijkstraRun(startVertex string) bool

DijkstraRun does the main relaxation pass starting from startVertex. After it returns, every reachable vertex has its Visited flag set, its cumulative Weight populated, its Parent pointer set, and the edges belonging to the shortest-path tree have their isShort flag set.

Returns false only if startVertex doesn't exist in the graph.

func (*StGraph) DijkstraSearch 

func (g *StGraph) DijkstraSearch(fromVertex, toVertex string) (bool, []StPath)

DijkstraSearch finds the shortest path from fromVertex to toVertex.

On success returns ok = true and a slice of StPath nodes ordered from source to destination, with cumulative Cost on each entry. On failure (either endpoint missing, no path, or the only path crosses a blocked vertex) returns ok = false and a nil slice.

Calling DijkstraSearch implicitly resets all per-vertex Dijkstra state on the graph. The graph's internal mutex is held for the full duration of the call, so concurrent calls on the same graph serialise (they remain safe -- no data races -- but do not run in parallel).

Example 
package main

import (
	"fmt"

	dijkstra "github.com/ultramcu/go-dijkstra"
)

func main() {
	var g dijkstra.StGraph

	// A directed graph:
	//
	//   A --1--> B --2--> C
	//   |                  ^
	//   +---------5--------+   (direct A->C, but slower)
	g.VertexAdd("A", 0, 0, 0,
		dijkstra.StEdge{ToVertexName: "B", Weight: 1, IsOneWay: true},
		dijkstra.StEdge{ToVertexName: "C", Weight: 5, IsOneWay: true},
	)
	g.VertexAdd("B", 1, 0, 0,
		dijkstra.StEdge{ToVertexName: "C", Weight: 2, IsOneWay: true},
	)
	g.VertexAdd("C", 2, 0, 0)

	ok, path := g.DijkstraSearch("A", "C")
	if !ok {
		fmt.Println("no path")
		return
	}
	for _, p := range path {
		fmt.Printf("%s (cost %.0f)\n", p.Name, p.Cost)
	}
}

Output:
A (cost 0)
B (cost 1)
C (cost 3)

func (*StGraph) DistanceCMToVertex 

func (g *StGraph) DistanceCMToVertex(x, y float64, name string) (bool, float64)

DistanceCMToVertex returns the cm distance from (x, y) to the vertex named `name`. Returns false, 0 if the vertex doesn't exist.

func (*StGraph) EdgeExist 

func (g *StGraph) EdgeExist(fromVertex, toVertex string) bool

EdgeExist reports whether an edge from fromVertex to toVertex exists.

func (*StGraph) EdgeGetWeight 

func (g *StGraph) EdgeGetWeight(fromVertex, toVertex string) float64

EdgeGetWeight returns the weight of the edge from fromVertex to toVertex, or 0 if no such edge exists.

func (*StGraph) EdgeIsOneWay 

func (g *StGraph) EdgeIsOneWay(fromVertex, toVertex string) bool

EdgeIsOneWay reports whether the edge from fromVertex to toVertex is marked one-way. Returns false if no such edge exists.

func (*StGraph) MaskShortEdge 

func (g *StGraph) MaskShortEdge(fromVertex, toVertex string) bool

MaskShortEdge marks the edge from fromVertex to toVertex as part of the shortest-path tree. Returns false if no such edge exists.

func (*StGraph) NearPoint 

func (g *StGraph) NearPoint(x, y float64) (string, float64)

NearPoint returns the name and distance (in cm) of the vertex whose (X, Y) is closest to (x, y). Returns "" and a very large number on an empty graph.

func (*StGraph) Print 

func (g *StGraph) Print()

Print writes the whole graph to stdout. It is shorthand for Show(os.Stdout); use Show to write to any io.Writer, or ShowFunc to customise the per-vertex format.

func (*StGraph) PrintDijkstra 

func (g *StGraph) PrintDijkstra()

PrintDijkstra writes every vertex's post-search state and its shortest-path-tree edges to stdout. Shorthand for ShowDijkstra(os.Stdout).

func (*StGraph) Show added in v1.7.1 

func (g *StGraph) Show(w io.Writer)

Show writes a human-readable dump of the whole graph -- every vertex with its coordinates, cumulative weight, visited flag and outgoing edges -- to w. Unlike Print (which targets stdout) it works with any io.Writer: a file, a bytes.Buffer in a test, or a log. Use ShowFunc to override the per-vertex formatting.

func (*StGraph) ShowDijkstra added in v1.7.1 

func (g *StGraph) ShowDijkstra(w io.Writer)

ShowDijkstra writes the post-search state of every vertex (cumulative weight, parent, visited) together with only the edges on the shortest-path tree to w. Call it after DijkstraSearch, DijkstraRun or an A* search.

func (*StGraph) ShowFunc added in v1.7.1 

func (g *StGraph) ShowFunc(w io.Writer, line func(v StVertex) string)

ShowFunc writes the graph to w, formatting each vertex with the caller-supplied line function -- so you can customise the output without re-implementing the iteration or the locking. Passing nil uses DefaultVertexLine (the same format as Show and Print).

line receives a copy of each vertex and should only format it: the graph's read lock is held while it runs, so do not call back into the graph (and do not mutate the vertex's Edges slice) from inside it.

func (*StGraph) VertexAdd 

func (g *StGraph) VertexAdd(name string, x, y, heading float64, edges ...StEdge) bool

VertexAdd inserts a new vertex with the given name, optional (x, y, heading) metadata, and zero or more outgoing edges.

Returns false if a vertex with this name already exists, or if any edge has a negative weight (Dijkstra requires non-negative weights).

Blocking is applied at search time, not here, so edges may be added in any order relative to VertexBLock / VertexBLockLoad.

func (*StGraph) VertexAddEdge added in v1.5.1 

func (g *StGraph) VertexAddEdge(fromVertex, toVertex string, weight float64, isOneWay bool) bool

VertexAddEdge adds an outgoing edge from an existing vertex to toVertex. As with VertexAdd, toVertex need not exist yet. Returns false if fromVertex does not exist, the weight is negative, or an edge from fromVertex to toVertex already exists.

func (*StGraph) VertexBLock 

func (g *StGraph) VertexBLock(name string) bool

VertexBLock adds an existing vertex to the blocked set. Returns false if name does not exist or is already blocked.

Example

ExampleStGraph_VertexBLock shows dynamic blocking: a vertex blocked at runtime makes the next search reroute around it. 

package main

import (
	"fmt"

	dijkstra "github.com/ultramcu/go-dijkstra"
)

func main() {
	var g dijkstra.StGraph
	g.VertexAdd("A", 0, 0, 0,
		dijkstra.StEdge{ToVertexName: "C", Weight: 1, IsOneWay: true},
		dijkstra.StEdge{ToVertexName: "B", Weight: 1, IsOneWay: true},
	)
	g.VertexAdd("B", 0, 0, 0, dijkstra.StEdge{ToVertexName: "D", Weight: 5, IsOneWay: true})
	g.VertexAdd("C", 0, 0, 0, dijkstra.StEdge{ToVertexName: "D", Weight: 1, IsOneWay: true})
	g.VertexAdd("D", 0, 0, 0)

	show := func(path []dijkstra.StPath) {
		out := ""
		for i, p := range path {
			if i > 0 {
				out += " -> "
			}
			out += p.Name
		}
		fmt.Println(out)
	}

	// Cheapest route is via C.
	_, path := g.DijkstraSearch("A", "D")
	show(path)

	// Block C at runtime; the next search reroutes via B.
	g.VertexBLock("C")
	_, path = g.DijkstraSearch("A", "D")
	show(path)

}

Output:
A -> C -> D
A -> B -> D

func (*StGraph) VertexBLockClear 

func (g *StGraph) VertexBLockClear()

VertexBLockClear empties the blocked-vertex set. The change takes effect on the next DijkstraSearch / DijkstraRun.

func (*StGraph) VertexBLockLoad 

func (g *StGraph) VertexBLockLoad(name []string) bool

VertexBLockLoad adds names to the blocked-vertex set. Always returns true.

func (*StGraph) VertexBLockRemove 

func (g *StGraph) VertexBLockRemove(name string) bool

VertexBLockRemove removes name from the blocked set. Returns true if the set was already empty or the name was removed, false if name was present in neither case.

func (*StGraph) VertexFind 

func (g *StGraph) VertexFind(name string) int

VertexFind returns the slice index of the vertex named `name`, or -1 if not found.

func (*StGraph) VertexGetParent 

func (g *StGraph) VertexGetParent(name string) string

VertexGetParent returns the parent name set during the last DijkstraRun, or "" if name doesn't exist or has no parent.

func (*StGraph) VertexGetWeight 

func (g *StGraph) VertexGetWeight(name string) float64

VertexGetWeight returns the cumulative cost recorded on the vertex during the last DijkstraRun, or 0 if the vertex doesn't exist.

func (*StGraph) VertexIsBLock 

func (g *StGraph) VertexIsBLock(name string) bool

VertexIsBLock reports whether name is currently in the blocked set.

func (*StGraph) VertexIsExist 

func (g *StGraph) VertexIsExist(name string) bool

VertexIsExist reports whether a vertex with that name exists.

func (*StGraph) VertexIsMasked 

func (g *StGraph) VertexIsMasked(name string) bool

VertexIsMasked reports whether a vertex has been touched by the path-reconstruction stack walk.

func (*StGraph) VertexIsVisited 

func (g *StGraph) VertexIsVisited(name string) bool

VertexIsVisited reports whether the vertex has been settled by the last DijkstraRun.

func (*StGraph) VertexLength 

func (g *StGraph) VertexLength() int

VertexLength returns the number of vertices in the graph.

func (*StGraph) VertexRemove added in v1.5.1 

func (g *StGraph) VertexRemove(name string) bool

VertexRemove deletes the named vertex from the graph together with every edge (from any vertex) that pointed at it, and drops it from the blocked set. Returns false if the vertex does not exist.

The next DijkstraSearch / DijkstraRun recomputes from scratch, so any stale Dijkstra state left on other vertices is harmless.

func (*StGraph) VertexRemoveEdge added in v1.5.1 

func (g *StGraph) VertexRemoveEdge(fromVertex, toVertex string) bool

VertexRemoveEdge removes the edge from fromVertex to toVertex. Returns false if fromVertex or the edge does not exist.

func (*StGraph) VertexSetMask 

func (g *StGraph) VertexSetMask(name string)

VertexSetMask marks a vertex as touched by the path-reconstruction stack walk.

func (*StGraph) VertexSetParent 

func (g *StGraph) VertexSetParent(child, parent string) bool

VertexSetParent records that `child`'s parent in the shortest-path tree is `parent`. Returns false if child doesn't exist.

func (*StGraph) VertexSetVisited 

func (g *StGraph) VertexSetVisited(name string)

VertexSetVisited marks a vertex as settled.

func (*StGraph) VertexSetWeight 

func (g *StGraph) VertexSetWeight(name string, weight float64)

VertexSetWeight overwrites the cumulative cost on a vertex.

func (*StGraph) VertexSetXY 

func (g *StGraph) VertexSetXY(name string, x, y float64)

VertexSetXY updates the X and Y coordinates of an existing vertex. No-op if the vertex doesn't exist.

func (*StGraph) VertexToStPath 

func (g *StGraph) VertexToStPath(name string) (bool, StPath)

VertexToStPath builds a snapshot StPath from the named vertex. Cost is taken from the vertex's current Weight (cumulative cost after a Dijkstra pass).

type StPath 

type StPath struct {
	Name    string
	X       float64
	Y       float64
	Heading float64
	Cost    float64
}

StPath is one node in a returned shortest path. Cost is the cumulative weight from the source up to and including this node.

type StPriorityQueue 

type StPriorityQueue struct {
	// contains filtered or unexported fields
}

StPriorityQueue is an ascending-by-weight priority queue of StPriorityQueueData implemented as a binary min-heap, so EnQueue and DeQueue are O(log n). Entries with equal weight are dequeued in insertion order (FIFO within an equivalence class).

func (*StPriorityQueue) Clear 

func (pq *StPriorityQueue) Clear()

Clear empties the queue.

func (*StPriorityQueue) DeQueue 

func (pq *StPriorityQueue) DeQueue() (bool, StPriorityQueueData)

DeQueue removes and returns the lowest-weight entry in O(log n). Returns (false, zero-value) if the queue is empty.

func (*StPriorityQueue) EnQueue 

func (pq *StPriorityQueue) EnQueue(fromVertex string, toVertex string, weight float64)

EnQueue inserts a new entry in O(log n).

func (*StPriorityQueue) Head 

func (pq *StPriorityQueue) Head() (bool, StPriorityQueueData)

Head returns the lowest-weight entry without removing it. Returns (false, zero-value) if the queue is empty.

func (*StPriorityQueue) Len 

func (pq *StPriorityQueue) Len() int

Len returns the number of entries currently in the queue.

func (*StPriorityQueue) NotEmpty 

func (pq *StPriorityQueue) NotEmpty() bool

NotEmpty is the negation of empty; convenient as a loop predicate.

func (*StPriorityQueue) Print 

func (pq *StPriorityQueue) Print()

Print writes the queue's contents to stdout in heap-array order.

type StPriorityQueueData 

type StPriorityQueueData struct {
	// contains filtered or unexported fields
}

StPriorityQueueData is one entry in the priority queue used by the Dijkstra relaxation pass: an edge (fromVertex -> toVertex) together with the cumulative cost to reach toVertex via that edge.

type StStack 

type StStack struct {
	// contains filtered or unexported fields
}

StStack is a simple LIFO stack of strings. Exported for users who want to do their own graph traversal on top of the StGraph types.

func (*StStack) Clear 

func (st *StStack) Clear()

Clear empties the stack.

func (*StStack) Empty 

func (st *StStack) Empty() bool

Empty reports whether the stack contains no entries.

func (*StStack) Len 

func (st *StStack) Len() int

Len returns the current depth of the stack.

func (*StStack) Pop 

func (st *StStack) Pop() string

Pop removes and returns the top of the stack. Returns "" if the stack is empty.

func (*StStack) Print 

func (st *StStack) Print()

Print writes the stack's contents to stdout in bottom-to-top order.

func (*StStack) Push 

func (st *StStack) Push(data string) bool

Push appends data to the top of the stack. Always returns true.

type StVertex 

type StVertex struct {
	Name       string
	Weight     float64
	Visited    bool
	X          float64
	Y          float64
	Heading    float64
	Edges      []StEdge
	MaskSearch bool
	Parent     string
}

StVertex is one node in the graph.

X / Y / Heading are optional metadata for spatial graphs. They are returned verbatim in StPath but are not consulted by the algorithm itself, so non-geometric users can leave them at zero.

Source Files

View all Source files

Directories

Path Synopsis
example
astar command
Command astar-example demonstrates AStarSearch on a spatial grid and shows that A*, guided by the straight-line heuristic, finds the same optimal path as Dijkstra while expanding far fewer vertices.
 Command astar-example demonstrates AStarSearch on a spatial grid and shows that A*, guided by the straight-line heuristic, finds the same optimal path as Dijkstra while expanding far fewer vertices.
compare command
Command compare is a runnable performance comparison of Dijkstra vs A* over grids of several sizes and two query shapes, printing the average time per search and the number of vertices each expands.
 Command compare is a runnable performance comparison of Dijkstra vs A* over grids of several sizes and two query shapes, printing the average time per search and the number of vertices each expands.
dijkstra command
Command dijkstra-example demonstrates DijkstraSearch on a small weighted directed graph, plus dynamic vertex blocking.
 Command dijkstra-example demonstrates DijkstraSearch on a small weighted directed graph, plus dynamic vertex blocking.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.