使用Dijkstra算法编写的Go程序寻找图的直径

什么是直径

在图论中，直径是指图中最短路径中的最大值。即，从图中任意两个顶点u和v之间的所有路径中，长度最长的一条路径的长度。

什么是Dijkstra算法

Dijkstra算法，又称单源最短路径算法，是典型的最优化算法。Dijkstra算法能够在有向图或者无向图中找到从一个顶点到其它所有顶点的最短路径。

如何使用Dijkstra算法找到图的直径

我们可以先使用Dijkstra算法找到图中任意一个顶点到其它所有顶点的最短路径，然后再对这些最短路径进行遍历，找到其中长度最长的一条，这条路径的长度即为图的直径。

以下是使用Dijkstra算法寻找图的直径的Go语言实现：

package main

import (
    "fmt"
    "math"
)

type Edge struct {
    to   int
    cost int
}

var G [][]Edge

func dijkstra(s int) []int {
    d := make([]int, len(G))
    for i := range d {
        d[i] = math.MaxInt32
    }
    d[s] = 0

    used := make([]bool, len(G))
    for i := range used {
        used[i] = false
    }

    for {
        v := -1
        for u := range G {
            if !used[u] && (v == -1 || d[u] < d[v]) {
                v = u
            }
        }
        if v == -1 {
            break
        }
        used[v] = true

        for _, e := range G[v] {
            if d[e.to] > d[v]+e.cost {
                d[e.to] = d[v] + e.cost
            }
        }
    }

    return d
}

func getDiameter() int {
    n := len(G)
    d := make([][]int, n)
    for i := range d {
        d[i] = dijkstra(i)
    }

    res := 0
    for i := range d {
        for j := range d[i] {
            if d[i][j] == math.MaxInt32 {
                continue
            }
            if d[i][j] > res {
                res = d[i][j]
            }
        }
    }

    return res
}

func main() {
    // 初始化图
    G = make([][]Edge, 4)
    G[0] = []Edge{{to: 1, cost: 10}, {to: 2, cost: 3}}
    G[1] = []Edge{{to: 0, cost: 10}, {to: 2, cost: 4}, {to: 3, cost: 2}}
    G[2] = []Edge{{to: 0, cost: 3}, {to: 1, cost: 4}, {to: 3, cost: 8}}
    G[3] = []Edge{{to: 1, cost: 2}, {to: 2, cost: 8}}

    diameter := getDiameter()
    fmt.Println(diameter)
}

运行上述程序，输出的结果为：