弗洛伊德算法和迪杰斯特拉算法

1.问题
用Floyd算法解出下图各个顶点的最短距离，写出Floyed算法的伪代码和给出距离矩阵

floyd算法又称差点法，是一种利用动态规划思想寻找给定加权图之间最短路径的算法。
状态转移方程：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
2.解析
Floyd算法：
设顶点集为v,边集为u
初始化：D[u,v]=A[u,v]
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即为所有点对的最短距离矩阵
3.设计
#头文件
#自定义常量
int 图的初始化
主函数{
定义常量
//
输入图的相关元素
//
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];
//
打印
//
}
4.分析
时间复杂度:O(n^3)
空间复杂度:O(n^2)
5.源码
https://github.com/joserfdave/arithmetic/blob/main/floyd

1.问题
对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径解析

2.设计
for(int i = 1;i <= n-1;++i){
min = inf;
int u;
for(int j = 1;j<= n; ++j){
if(book[j]==0&&dis[j]min = dis[j];
u = j;
}
}
book[u] = 1;
for(int v = 1;v <= n;++v){
if(edge[u][v] < inf){
if (dis[v] > dis[u] + edge[u][v])
dis[v] = dis[u] + edge[u][v];
}
}
}
3.分析
该算法复杂度为O(n^2)
4.源码
https://github.com/joserfdave/arithmetic/blob/main/dijkstra