多源最短路径

Question

如题所述

Answer 1

在连接两点的线中，线段是最短的，这条线段的长度，是这两点之间的距离。
从直线外一点向直线上的各点，连接的线段里，垂线段是最短的，这条垂线段的长度，是这一点到直线的距离。
从一条直线的一点到另一条和它平行的直线上的各点，连接的线段里，和这两条平行线垂直的线段最短，线段的长度叫做两条平行线之间的距离。平行线之间的距离都相等。
希望我能帮助你解疑释惑。

Answer 2

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
简单的来说，算法的主要思想是动态规划(dp)，而求最短路径需要不断松弛(熟悉spfa算法的可能熟悉松弛)。
而算法的具体思想为：
邻接矩阵dist储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！而自己的长度为0.
从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
而上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。
重复上述直到最后插点试探完成。
其中第三步的状态转移方程为:
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
其中dp[x][y]的意思可以理解为x到y的最短路径。所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思可以理解为k到j的最短路径.

对于程序而言，这个插入的过程相当简单。核心代码只有四行！
代码如下
#include
#include
using namespace std;
#define maxn 1000
int dist[1000][1000];

void floyd(int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if( i == j ) dist[i][j] = 0;
else dist[i][j] = 0x7fffffff;
}
}
for (int k = 1; k <= n; k++) //k一定是在最外层，第k次循环dist[i][j]表示i到j允许经过0~k节点作为中转的最短花费
{
for (int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}