graph

func (*Graph) AddEdge ¶

func (g *Graph) AddEdge(tail, head *Vertex, weight int)

func (*Graph) AddVertex ¶

func (g *Graph) AddVertex(label string) *Vertex

func (*Graph) BellmanFordShortestPath ¶

func (g *Graph) BellmanFordShortestPath(source *Vertex) (map[string]int, error)

An implementation of Bellman-Ford shortest path distance algorithm. The algorithm uses a variation of dynamic programming to produce a shortest path weight for each vertex relative to the given source. In the event of a negative cycle it returns nil with an error of a negative cycle.

func (*Graph) DijkstrasShortestPath ¶

func (g *Graph) DijkstrasShortestPath(source *Vertex) map[string]int

"A blazingly fast shortest path algorithm" as Tim Roughgarden would put it, Dijkstra's Algorithm computes the shortest path from a given source vertex and all vertices within the graph. A value of math.MaxInt32 is used to represent infinity when a vertex is not reachable from the given source vertex.

func (*Graph) FloydWarshallAllShortestPath ¶

func (g *Graph) FloydWarshallAllShortestPath() (map[string]map[string]int, error)

func (*Graph) JohnsonsAllShortestPath ¶

func (g *Graph) JohnsonsAllShortestPath() (map[string]map[string]int, error)

Johnsons algorithm is an all shortest path algorithm which provides weights of shortest paths from all vertices within the graph. The function returns a map vertex labels as keys and their sink maps keyed by sink labels. If the graph contains a negative cycle the function will return a nil result with an appropriate error.