Dijkstra 算法、Kruskal 算法、Prim算法、floyd算法

1、dijkstra算法

算最短路径的，算法解决的是有向图中单个源点到其他顶点的最短路径问题。

初始化n*n的数组。

2、kruskal算法

算最小生成树的,按权值加入

3、Prim算法

类似dijkstra算法，任一点的最短路径相似

4、floyd算法多源最短路径，动态规划

a)　初始化：D[u,v]=A[u,v]
b)　 For k:=1 to n
　　　　For i:=1 to n
　　　　　　For j:=1 to n
　　　　　　　　If D[i,j]>D[i,k]+D[k,j] Then
　　　　　　　　D[i,j]:=D[i,k]+D[k,j];
c)　算法结束：D即为所有点对的最短路径矩阵

巴特西

Dijkstra 算法、Kruskal 算法、Prim算法、floyd算法

最新文章

热门文章