go最短路

本文主要是介绍go最短路，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：https://acm.hdu.edu.cn/showproblem.php?pid=2544

package main

import (
	"fmt"
	"math"
)

var (
	n int //n个点
	m int //m条边
	edge [][]int
)

func dij(st, ed int) {
	vis := make([]bool, n)
	dis := make([]int, n)
	for i := 0; i < n; i++ {
		dis[i] = edge[st][i]
	}
	vis[st] = true
	for i := 0; i < n; i++ {
		if vis[ed] {
			break
		}
		minn := math.MaxInt64
		v := -1
		for j := 0; j < n; j++ {
			if !vis[j] && dis[j] < minn {
				minn = dis[j]
				v = j
			}
		}
		vis[v] = true
		for j := 0; j < n; j++ {
			if !vis[j] && dis[v] + edge[v][j] < dis[j] {
				dis[j] = dis[v] + edge[v][j]
			}
		}
	}
	fmt.Println(dis[ed])
}

func main() {
	for {
		fmt.Scanf("%d %d", &n, &m)
		if n == 0 && m == 0 {
			break
		}
		edge = make([][]int, n)
		for i := 0; i < n; i++ {
			edge[i] = make([]int, n)
		}
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if i == j {
					edge[i][j] = 0
				} else {
					edge[i][j] = math.MaxInt64
				}
			}
		}
		for i := 0; i < m; i++ {
			var (
				a int
				b int
				c int
			)
			fmt.Scanf("%d %d %d", &a, &b, &c)
			a--
			b--
			edge[a][b] = int(math.Min(float64(edge[a][b]), float64(c)))
			edge[b][a] = edge[a][b]
		}
		//fmt.Println(edge)
		dij(0, n - 1)
	}
}

这篇关于go最短路的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！