最短路径算法

最短路径

我们把边具有权重的图称为带权图，权重可以理解为两点间的距离。一个图中任意两点会有多条路径联通，最短路径就是这些路径中最短的一条。

负环：环中所有边权之重和小于0的环

Floyed算法

算法思想

如何让两个点（假设a到b）的距离变短，只能引入第三个点k，通过k进行中转即a->k->b，当然中转点可以是多个。

算法分析

使用邻接矩阵E保存图，每个格子E(i, j)表示点i到点j的最短距离，不相邻的距离为Infinity。遍历每一个点作为中转点k，更新点i与点j的最短路径。

const E: number[][] = []
for(let k=1; i<=n; i++){ // 遍历中转点
	// 点i到点j的最短距离更新
	for(let i=1; i<=n; i++) { 
		for(let j=1; j<=n; j++) {
			E[i][j] = Math.min(E[i][j], E[i,k]+E[k,j])
		}
	}
}

算法总结

时间复杂度：O(n^3)
Floyed算法适用于有负权边的图；但不适用于有负权环的图。