Rosetta Code

Floyd-Warshall algorithm: Difference between revisions

Page Discussion

Floyd-Warshall algorithm (view source)

Revision as of 03:35, 2 November 2018

147 bytes added ,  5 years ago
m
Convert tabs to spaces.
m (spelling)
m (Convert tabs to spaces.)
Line 745:
=={{header|Go}}==
<lang go>package main
 
import (
"fmt"
"strconv"
)
 
// A Graph is the interface implemented by graphs that
// this algorithm can run on.
type Graph interface {
Vertices() []Vertex
Neighbors(v Vertex) []Vertex
Weight(u, v Vertex) int
}
 
// Nonnegative integer ID of vertex
type Vertex int
 
// ig is a graph of integers that satisfies the Graph interface.
type ig struct {
vert []Vertex
edges map[Vertex]map[Vertex]int
}
 
func (g ig) edge(u, v Vertex, w int) {
if _, ok := g.edges[u]; !ok {
g.edges[u] = make(map[Vertex]int)
}
g.edges[u][v] = w
}
func (g ig) Vertices() []Vertex { return g.vert }
func (g ig) Neighbors(v Vertex) (vs []Vertex) {
for k := range g.edges[v] {
vs = append(vs, k)
}
return vs
}
func (g ig) Weight(u, v Vertex) int { return g.edges[u][v] }
func (g ig) path(vv []Vertex) (s string) {
if len(vv) == 0 {
return ""
}
s = strconv.Itoa(int(vv[0]))
for _, v := range vv[1:] {
s += " -> " + strconv.Itoa(int(v))
}
return s
}
 
const Infinity = int(^uint(0) >> 1)
 
func FloydWarshall(g Graph) (dist map[Vertex]map[Vertex]int, next map[Vertex]map[Vertex]*Vertex) {
vert := g.Vertices()
dist = make(map[Vertex]map[Vertex]int)
next = make(map[Vertex]map[Vertex]*Vertex)
for _, u := range vert {
dist[u] = make(map[Vertex]int)
next[u] = make(map[Vertex]*Vertex)
for _, v := range vert {
dist[u][v] = Infinity
}
}
dist[u][u] = 0
for _, v := range g.Neighbors(u) {
v := v
dist[u][v] = g.Weight(u, v)
next[u][v] = &v
}
}
}
for _, k := range vert {
for _, i := range vert {
for _, j := range vert {
if dist[i][k] < Infinity && dist[k][j] < Infinity {
if dist[i][j] > dist[i][k]+dist[k][j] {
dist[i][j] = dist[i][k] + dist[k][j]
next[i][j] = next[i][k]
}
}
}
}
}
}
}
}
}
return dist, next
}
 
func Path(u, v Vertex, next map[Vertex]map[Vertex]*Vertex) (path []Vertex) {
if next[u][v] == nil {
return
}
path = []Vertex{u}
for u != v {
u = *next[u][v]
path = append(path, u)
}
return path
}
 
func main() {
g := ig{[]Vertex{1, 2, 3, 4}, make(map[Vertex]map[Vertex]int)}
g.edge(1, 3, -2)
g.edge(3, 4, 2)
g.edge(4, 2, -1)
g.edge(2, 1, 4)
g.edge(2, 3, 3)
 
dist, next := FloydWarshall(g)
fmt.Println("pair\tdist\tpath")
for u, m := range dist {
for v, d := range m {
if u != v {
fmt.Printf("%d -> %d\t%3d\t%s\n", u, v, d, g.path(Path(u, v, next)))
}
}
}
}
}
}</lang>
{{out}}
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/261961"