package Dijkstra
import (
"container/heap"
"math"
)
type Egraph struct {
Nv int
Ne int
Edges []Edge
}
type Graph struct {
Nv int
G [][]int
}
type Edge struct {
Start int
End int
Value int
}
type PriorityQueue []*Edge
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].Value < pq[j].Value
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
item := x.(*Edge)
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func Dijkstra(g *Graph, s int) ([]int, []int) {
var p PriorityQueue = make([]*Edge, 0, g.Nv)
dis := make([]int, g.Nv)
form := make([]int, g.Nv)
mark := make([]bool, g.Nv)
p.Push(&Edge{Start: s, End: s, Value: 0})
dis[s] = 0
for i := 1; i < len(dis); i++ {
dis[i] = math.MaxInt64
}
mark[s] = true
count := 0
for {
t := heap.Pop(&p).(*Edge)
if dis[t.End] > dis[t.Start]+t.Value {
dis[t.End] = dis[t.Start] + t.Value
form[t.End] = t.Start
mark[t.End] = true
}
count++
if count == g.Nv {
break
}
p = p[:0]
for i := 0; i < g.Nv; i++ {
if !mark[i] && g.G[t.End][i] != 0 {
heap.Push(&p, &Edge{Start: t.End, End: i, Value: g.G[t.End][i]})
}
}
}
return dis, form
}
func BellmanFord(g *Egraph, s int) ([]int, []int, bool) {
dis := make([]int, g.Nv)
form := make([]int, g.Nv)
dis[s] = 0
for i := 1; i < len(dis); i++ {
dis[i] = math.MaxInt64
}
flag := false
for i := 0; i < g.Nv; i++ {
for j := 0; j < g.Ne; j++ {
f, t := g.Edges[j].Start, g.Edges[j].End
if dis[f] != math.MaxInt64 && dis[t] > dis[f]+g.Edges[j].Value {
dis[t] = dis[f] + g.Edges[j].Value
form[t] = f
}
}
}
for j := 0; j < g.Ne; j++ {
f, t := g.Edges[j].Start, g.Edges[j].End
if dis[f] != math.MaxInt64 && dis[t] > dis[f]+g.Edges[j].Value {
flag = true
break
}
}
return dis, form, flag
}
func FloydWarshall(g *Graph) [][]int {
dis := make([][]int, g.Nv)
for i := 0; i < g.Nv; i++ {
dis[i] = make([]int, g.Nv)
for j := 0; j < g.Nv; j++ {
if i!=j && g.G[i][j] == 0 {
dis[i][j] = math.MaxInt64
} else {
dis[i][j] = g.G[i][j]
}
}
}
for i := 0; i < g.Nv; i++ {
for j := 0; j < g.Nv; j++ {
for k := 0; k < g.Nv; k++ {
if dis[i][j]-dis[i][k] > dis[k][j] {
dis[i][j] = dis[i][k] + dis[k][j]
}
}
}
}
return dis
}
// test
package Dijkstra
import "testing"
func TestDijkstra(t *testing.T) {
g := Graph{
4,
[][]int{
{0, 1, 3, 5},
{1, 0, 1, 0},
{3, 1, 0, 1},
{5, 0, 1, 0},
},
}
t.Log(Dijkstra(&g, 0))
}
func TestBellmanFord(t *testing.T) {
g := Egraph{
4, 10,
[]Edge{
{0, 1, 1},
{1, 0, 1},
{1, 2, 1},
{2, 1, 1},
{0, 2, 3},
{2, 0, 3},
{2, 3, 1},
{3, 2, 1},
{0, 3, 5},
{3, 0, 5},
},
}
t.Log(BellmanFord(&g, 0))
}
func TestFloydWarshall(t *testing.T) {
g := Graph{
4,
[][]int{
{0, 1, 3, 5},
{1, 0, 1, 0},
{3, 1, 0, 1},
{5, 0, 1, 0},
},
}
t.Log(FloydWarshall(&g))
}
原文：https://www.cnblogs.com/weiweng/p/13528564.html