作业2：Floyd算法和Dijkstra算法

1. 问题

最小路径问题。也就是在一个图中，从A出发走向所有的顶点，分别找一条路径，使得点A到各个顶点之间的距离最小。也就是说，如果除了A以外有8个顶点，那么就需要找到8条路径。

1. 解析

Floyd算法：通过不断增加可以经过的点来己算一个点到其他点的最短距离。

 

对于上述的有向图，假如不允许任何中间结点，距离如下图：

 

如果允许经过点1：

 

如果允许经过点1和2：

 

以此类推，如果可以经过所有的点：

 

Dijkstra算法：

引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是"起点s到该顶点的路径"。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。

 

 

 

以此类推,如果遇到走更多的边反而路径更短的，则选择路径更短的边：

 

其余的点算法也类似

 

 

1. 设计

Floyd算法：

for(k=1;k<=n;k++) 

    for(i=1;i<=n;i++) 

    for(j=1;j<=n;j++) 

    if(e[i][j]>e[i][k]+e[k][j]) 

                     e[i][j]=e[i][k]+e[k][j];

Dijkstra算法：

当Q不为空的情况下，取出堆顶的元素(v, [dist[v]) —— 也就是当前距离s最近的结点v，及其距离dist[v]。

如果v在S中，则代表我们已经访问过v的最短路径。那么跳过当前v，重复步骤1。

否则，将v放在S中。

对于每一个与v相邻的结点t：

如果dist[v] + weight(v, t) < dist[t]，则更新dist[t] = dist[v] + weight(v, t)。同时将(t, dist[t])放进Q中。

否则，不做任何处理。

当算法结束后，dist[]中保存图中每一个除s之外的结点到s的最短路径的权重值（或长度）。如果从s到v不存在联通的路径，则dist[v] = ∞。

 

1. 分析

Floyd算法：由于是三重循环：O(n^3)

时间复杂度为O(n^2)

 

1. 源码

https://github.com/cyy1176489683/Design-and-analysis-of-algorithms/tree/master/homework2