论文题目
对任意点对间的最短路径算法的思考
姓名
学院
学号
日期
对任意点对间的最短路径算法的思考
算法的设计与分析最重要的是要对所描述问题有一个清晰的认识和整体的思路，运用所学的知识，通过不断的探索、比较，找到针对问题的最优化的算法。本文是对任意点对间的最短路径算法的学习领会。
全源点对最短路径是单源最短路径的推广与延伸，所以两者的算法也有是相通之处。因为一个图中如果有负权边环存在的话，那么最短路径路就有可能不会存在，因此对于存在有负权重边的图来说，一定要能判断出它的存在，如果能求出最短的路径，最好能给出解法。在单源最短路径算法中，Bellman-Ford 算法可以判断负权重的环是否存在。
Bellman-Ford 算法的伪码：
1. d[s] ← 0
2. for each v ∈ V – {s}
3. do d[v] ← ∞
4. for i ← 1 to | V | – 1
5. do for each edge (u, v) ∈ E
6. do if d[v] > d[u] + w(u, v)
7. then d[v] ← d[u] + w(u, v)
8. for each edge (u, v) ∈ E
9. do if d[v] > d[u] + w(u, v)
10. then report that a negative-weight cycle exists
1~3是初始化操作；4~7是对边的松弛操作；8~10是对图中是否有负权环存在的判断。
算法，就是解决某类问题的一系列步骤。算法的最大特征就是分步，并且每个步骤都是明确的、可行的，而且能在有限步骤内完成。
课本上介绍了三种全源点对路径的算法：动态规划的算法、
Floyd-Warshall 算法和Johnson 算法。
动态规划的算法的思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原始问题的解。由优化准则可知最优解一定存在。值得注意的地方是教授将矩阵乘法的表示方法用于表示算法，而且使时间复杂度降低（Θ(n4)），而通过对矩阵的改进可以使时间进一步降低（Θ(n3lg n) ），这种思想是非常值得学习的！
Floyd-Warshall 算法也是一种动态规划算法，时间复杂度更低（Θ(n3)），是对原始动态规划算法的改进。这种算法代码简单，效率高。 另外利用有向图的传递闭包表示方法会很方便，而且时间复杂度不会改变。
Johnson 算法是通过对原始图的边进行重新赋权重，通过任意两个顶点的路径调整相同的权值，从而使每个定点都拥有一定的权值，然后利用Bellman-Ford 算法解决不同的约束条件问题，或者判断负环的存在，接着对每个顶点运行Dijkstra 算法，总的运行时间是O(VE+V2lg V)，可见Johnson 算法时间复杂度已经大大降低，不过这是以算法的复杂性来作为代价的。因此，设计算法时要综合多种因素，综合判断需要设计什么样的计算方法。
以上三种方法都是针对全源点对最短路径的算法，可以看出，全源点对最短路径是对单源最短路径的延伸，我们对图中的每个点都进行单源最短路径算法的运行就可以求得全源点对的最短路径。这是最原始的想法，然后我们要做的就是对算法的改进和提升工作，这时也是对自己最大的考验，因为它要综合运用所学的知识，是一个演绎升华的过程。
通过对任意点对间的最短路径算法的学习，我对算法的设计有了很大一步的认识，算法设计立足于用自然语言描述解决实际问题，明确的过程顺序是实现用程序框图、程序语言的表示方式的基础，此外就是对时间问题复杂度的分析，时间复杂度越低越好。学习的过程中令我印象最深的地方是教授将矩阵和传递闭包的运算性质运用到算
法中，我们利用矩阵和传递闭包的的表示形式和运算性质，通过对其运算符号进行改进，使它们演变为表示算法的符号，这种思想是极其重要的。在以后的学习过程中尤其要注意这方面的锻炼。
算法设计有利于培养我们清晰的思维，使我们更有条理地处理事情，同时，它在科学领域中应用广泛，特别是在计算机程序方面。以下是我对算法学习的总结：1. 基础算法要扎实，现在感觉到仍然需要学习基础的算法思想，很多大型、复杂的算法都是以简单算法为基础的；2. 知识面要广，算法的设计过程中可能会借鉴很多其他专业、学科的知识，多读多写多思考，灵活运用；3. 勇于创新，创新是解决很多问题的重要途径。
论文题目
对任意点对间的最短路径算法的思考
姓名
学院
学号
日期
对任意点对间的最短路径算法的思考
算法的设计与分析最重要的是要对所描述问题有一个清晰的认识和整体的思路，运用所学的知识，通过不断的探索、比较，找到针对问题的最优化的算法。本文是对任意点对间的最短路径算法的学习领会。
全源点对最短路径是单源最短路径的推广与延伸，所以两者的算法也有是相通之处。因为一个图中如果有负权边环存在的话，那么最短路径路就有可能不会存在，因此对于存在有负权重边的图来说，一定要能判断出它的存在，如果能求出最短的路径，最好能给出解法。在单源最短路径算法中，Bellman-Ford 算法可以判断负权重的环是否存在。
Bellman-Ford 算法的伪码：
1. d[s] ← 0
2. for each v ∈ V – {s}
3. do d[v] ← ∞
4. for i ← 1 to | V | – 1
5. do for each edge (u, v) ∈ E
6. do if d[v] > d[u] + w(u, v)
7. then d[v] ← d[u] + w(u, v)
8. for each edge (u, v) ∈ E
9. do if d[v] > d[u] + w(u, v)
10. then report that a negative-weight cycle exists
1~3是初始化操作；4~7是对边的松弛操作；8~10是对图中是否有负权环存在的判断。
算法，就是解决某类问题的一系列步骤。算法的最大特征就是分步，并且每个步骤都是明确的、可行的，而且能在有限步骤内完成。
课本上介绍了三种全源点对路径的算法：动态规划的算法、
Floyd-Warshall 算法和Johnson 算法。
动态规划的算法的思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原始问题的解。由优化准则可知最优解一定存在。值得注意的地方是教授将矩阵乘法的表示方法用于表示算法，而且使时间复杂度降低（Θ(n4)），而通过对矩阵的改进可以使时间进一步降低（Θ(n3lg n) ），这种思想是非常值得学习的！
Floyd-Warshall 算法也是一种动态规划算法，时间复杂度更低（Θ(n3)），是对原始动态规划算法的改进。这种算法代码简单，效率高。 另外利用有向图的传递闭包表示方法会很方便，而且时间复杂度不会改变。
Johnson 算法是通过对原始图的边进行重新赋权重，通过任意两个顶点的路径调整相同的权值，从而使每个定点都拥有一定的权值，然后利用Bellman-Ford 算法解决不同的约束条件问题，或者判断负环的存在，接着对每个顶点运行Dijkstra 算法，总的运行时间是O(VE+V2lg V)，可见Johnson 算法时间复杂度已经大大降低，不过这是以算法的复杂性来作为代价的。因此，设计算法时要综合多种因素，综合判断需要设计什么样的计算方法。
以上三种方法都是针对全源点对最短路径的算法，可以看出，全源点对最短路径是对单源最短路径的延伸，我们对图中的每个点都进行单源最短路径算法的运行就可以求得全源点对的最短路径。这是最原始的想法，然后我们要做的就是对算法的改进和提升工作，这时也是对自己最大的考验，因为它要综合运用所学的知识，是一个演绎升华的过程。
通过对任意点对间的最短路径算法的学习，我对算法的设计有了很大一步的认识，算法设计立足于用自然语言描述解决实际问题，明确的过程顺序是实现用程序框图、程序语言的表示方式的基础，此外就是对时间问题复杂度的分析，时间复杂度越低越好。学习的过程中令我印象最深的地方是教授将矩阵和传递闭包的运算性质运用到算
法中，我们利用矩阵和传递闭包的的表示形式和运算性质，通过对其运算符号进行改进，使它们演变为表示算法的符号，这种思想是极其重要的。在以后的学习过程中尤其要注意这方面的锻炼。
算法设计有利于培养我们清晰的思维，使我们更有条理地处理事情，同时，它在科学领域中应用广泛，特别是在计算机程序方面。以下是我对算法学习的总结：1. 基础算法要扎实，现在感觉到仍然需要学习基础的算法思想，很多大型、复杂的算法都是以简单算法为基础的；2. 知识面要广，算法的设计过程中可能会借鉴很多其他专业、学科的知识，多读多写多思考，灵活运用；3. 勇于创新，创新是解决很多问题的重要途径。