dijkstra

Documentation

Index

• func DefaultCostGetter(g *Graph, source, target int) int
• type CostGetter
• type Graph
  • func NewEmptyGraph() *Graph
  • func NewGraph(vs []*Vertex) *Graph
  • func (g *Graph) AddEdge(src, dst, w int) bool
  • func (g *Graph) AddVertex() int
  • func (g *Graph) AllShortestPath(source, target int, cg CostGetter) [][]int
  • func (g *Graph) GetAllNeighbours(source int) []int
  • func (g *Graph) GetAllVertices() []*Vertex
  • func (g *Graph) HasEdge(source, target int) bool
  • func (g *Graph) Len() int
  • func (g *Graph) PrintGraph()
  • func (g *Graph) RemoveEdge(src, dst int) bool
• type Vertex

Functions

func DefaultCostGetter

func DefaultCostGetter(g *Graph, source, target int) int

DefaultCostGetter default cost getter

Types

type CostGetter

type CostGetter func(g *Graph, source, target int) (weight int)

CostGetter weight前提肯定大于０

type Graph

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

Graph graph's vertex should be from 0 to n-1 when there are n vertices

func NewEmptyGraph

func NewEmptyGraph() *Graph

NewEmptyGraph new a empty graph

func NewGraph

func NewGraph(vs []*Vertex) *Graph

NewGraph new a whole graph for all nodes(Vertex)

func (*Graph) AddEdge

func (g *Graph) AddEdge(src, dst, w int) bool

AddEdge add a edge(one connection) to redraw the graph

func (*Graph) AddVertex

func (g *Graph) AddVertex() int

AddVertex add a node for the graph

func (*Graph) AllShortestPath

func (g *Graph) AllShortestPath(source, target int, cg CostGetter) [][]int

AllShortestPath Computes all shortest paths between 2 vertices source: starting vertex ,target: end vertex

func (*Graph) GetAllNeighbours

func (g *Graph) GetAllNeighbours(source int) []int

GetAllNeighbours return all neighbor nodes

func (*Graph) GetAllVertices

func (g *Graph) GetAllVertices() []*Vertex

GetAllVertices return all vertices

func (*Graph) HasEdge

func (g *Graph) HasEdge(source, target int) bool

HasEdge has or not has a direct connection

func (*Graph) Len

func (g *Graph) Len() int

Len return the nodes' number

func (*Graph) PrintGraph

func (g *Graph) PrintGraph()

PrintGraph for debug a graph

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(src, dst int) bool

RemoveEdge remove a neighbor node

type Vertex

type Vertex struct {
	ID   int
	Arcs map[int]int
}

Vertex, Arcs[vertex ID] = weight