graph

Documentation

Index

• type Graph
• type Vertex
  • func ShortestPath(g Graph, start, end Vertex) []Vertex

Types

type Graph

type Graph interface {
	// NumVertex returns the number of vertices in the graph.
	NumVertex() int

	// VertexID returns a vertex ID, 0 <= ID < NumVertex(), for v.
	VertexID(v Vertex) int

	// Neighbors returns a slice of vertices that are adjacent
	// to v in the graph.
	Neighbors(v Vertex) []Vertex
}

A Graph is the interface implemented by graphs that this package can run algorithms on.

type Vertex

type Vertex interface {
	String() string
}

func ShortestPath

func ShortestPath(g Graph, start, end Vertex) []Vertex

ShortestPath uses Dijkstra's algorithm to find the shortest path from start to end in g. It returns the path as a slice of vertices, with start first and end last. If there is no path, ShortestPath returns nil.