最短路径算法-Floyd

在上一篇当中讲了 Dijkstra 算法,Dijkstra 适用于对于单源路径的求取,但是对于任意两个点之间的最小路径呢?首先想到的当然是直接使用多次的 Dijkstra 算法来求取任意两点之间的最短路径,但是这样下来时间复杂度会比较大,所以使用一种新的算法,Floyd 算法来求取最短路径

原理

Floyd 算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点 i 到点 j 的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释
从任意节点 i 到任意节点 j 的最短路径不外乎 2 种可能:

  • 1.直接从 i 到 j,
  • 2.从 i 经过若干个节点 k 到 j。
    所以,我们假设 Dis(i,j)为节点 u 到节点 v 的最短路径的距离,对于每一个节点 k,我们检查 Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短,我们便设置 Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点 k,Dis(i,j)中记录的便是 i 到 j 的最短路径的距离。

算法描述:

a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。   
b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

Golang 实现

package ShortestPath

import (
	"errors"

	"github.com/mohuishou/algorithm/GraphMatrix"
)

//Floyd 求取多源最短路径
func Floyd(graph GraphMatrix.Graph, dist [][]GraphMatrix.EdgeType, path [][]int) error {
	for i := 0; i < graph.VNum; i++ {
		for j := 0; j < graph.VNum; j++ {
			path[i][j] = -1
			dist[i][j] = graph.G[i][j]
		}
	}

    //注意,k必须放在最外层,如果放在最里层会过早的确认两点的最短路径
	for k := 0; k < graph.VNum; k++ {
		for i := 0; i < graph.VNum; i++ {
			for j := 0; j < graph.VNum; j++ {

				//找到更短的路径
				if dist[i][k]+dist[k][j] < dist[i][j] {
					dist[i][j] = dist[i][k] + dist[k][j]

					//发现负值圈
					if i == j && dist[i][j] < 0 {
						return errors.New("存在负值圈")
					}
					path[i][j] = k
				}
			}
		}
	}
	return nil
}

//GetPathForFloyd 获取路径
func GetPathForFloyd(path [][]int, s, t int) (tPath []int) {
	tPath = make([]int, 1)
	tPath[0] = s
	for {
		s = path[s][t]
		if s == -1 || s == t {
			tPath = append(tPath, t)
			return tPath
		}
		tPath = append(tPath, s)
	}
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!