Go 解决最短路径问题

最短路径问题

wiki:最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

图解

代码

package main

import "fmt"

func minPath(matrix [][]int) int {
	if matrix == nil || len(matrix)==0 || matrix[0]==nil || len(matrix[0])==0 {
		return 0
	}

	row := len(matrix)
	col := len(matrix[0])
	dp := make([][]int, row)

	for i := range dp {
		dp[i] = make([]int, col)
	}

	dp[0][0] = matrix[0][0]

	for i := 1; i < row; i++ {
		dp[i][0] = dp[i-1][0]+matrix[i][0]
	}

	for j := 1; j < col; j++ {
		dp[0][j] = dp[0][j-1]+matrix[0][j]
	}

	for i := 1; i < row; i++ {
		for j := 1; j < col; j++ {
			if dp[i-1][j] > dp[i][j-1] {
                dp[i][j] = dp[i][j-1]+matrix[i][j]
            } else {
            	dp[i][j] = dp[i-1][j]+matrix[i][j]
            }
		}
	}

	return dp[row-1][col-1]
}

func main() {
	m := [][]int{
		{2,5,3,5},
		{7,1,3,4},
		{4,2,1,6},
	}
	fmt.Printf("最短路径：%v",minPath(m))
}

执行

$ go run minPath.go
最短路径：17

关联

[[Java 解决最短路径问题]]
[[PHP 解决最短路径问题]]