最短路径——Floyd算法与Dijkstra算法

Floyd算法，也被叫做插点法，可以解决多源最短路径的问题，即通过在两个目标点之间插入第三个点作为中转点，从而达到缩短目标点之间距离的目的

（利用《啊哈！算法》一书中的图片更有助于理解

箭头标记的数字为两点之间的距离，我们可以发现通过某个点可以是另外两个点之间的距离减小，且不影响它们之间的连通性

我们用一个二维数组map[I][j]存储上图，i，j任意两点的序号，map[I][j]的值为这两点间的距离

可得到Floyd算法的核心代码（不难理解哟）

for(int k=1;k<=n;k++)
   for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     {
         if(map[i][j]>map[i][k]+map[k][j])
             map[i][j]>map[i][k]+map[k][j];
     }

(算法虽简单，但时间复杂度为O(N)^3,无时间限制可以使用，否则容易超时）

HDU2066——一个人的旅行(我用Floyd疯狂超时。。，最后对照大佬的算法水过~~）

#include<cstdio>
#include<algorithm>
#define inf 99999999
bool be[1001], en[1001];
int map[1001][1001];
int max_flag;
int floyd()
{
 int MIN = inf;
 for(int k=1;k<=max_flag;++k)
  for(int i=1;i<=max_flag;++i)
   if (map[i][k] != inf)//优化，若这两个点之间无路连接，则不能作为中转路线
   {
    for (int j = 1; j <= max_flag; ++j)
    {
     map[i][j] = map[i][j]<map[i][k]+map[k][j]?map[i][j]: map[i][k] +map[k][j];//更新两点的最小距离
     if (be[i] && en[j]&& MIN > map[i][j])
      MIN = map[i][j];
    }
   }
 return MIN;
}
int main()
{
 int T, S, D, a, b, c, x, y;//x为起点,y为终点
 while (scanf_s("%d%d%d", &T, &S, &D) != EOF)
 {
  for (int i = 1; i <= 1000; ++i)
   for (int j = 1; j <= 1000; ++j)
    map[i][j] = inf;//不知是不是数组太大的原因，用memset会超时，并且inf一大数据就会溢出，往哪位路过的大佬解答
  max_flag = 0;
  for (int i = 1; i <= T; ++i)
  {
   scanf_s("%d%d%d", &a, &b, &c);
   max_flag = max_flag < b ? b : max_flag;
   max_flag = max_flag < a ? a : max_flag;
   //max_flag = max(max(max_flag, a), b);//记录标号最大的一点，确定计算的范围
   map[a][b] = map[b][a] = map[a][b] < c ? map[a][b] : c;
   //map[a][b] = map[b][a] = max(map[a][b], c);
  }
  memset(be, false, sizeof(be));
  memset(en, false , sizeof(en));
  for (int j = 1; j <= S; ++j)
  {
   scanf_s("%d", &x);
   be[x] = true;
  }
  for (int k = 1; k <= D;++k)
  {
   scanf_s("%d", &y);
   en[y] = true;
  }
  printf("%d\n", floyd());
 }
 return 0;
}

Dijkstra算法(单源最短路径O(N)^2)，用一个一维数组存储起点到目标点的距离，用二维数组通过中转点对距离进行更新

该题的Dijkstra算法

#include<cstdio>
#include<algorithm>
using namespace std;
const int inf = 0x3fffffff;
int map[1010][1010];
int dis[1010];//dis[i]记录起点到点i的距离
int book[1010];//记录该点是否与起点连接
int st[1010], en[1010];
int n,flag;
void Dijkstra()
{
 int i, j,k, MIN;
 for (i = 1; i <=n; i++)
 {
  MIN = inf;
  for (j = 1; j <= n; j++)//找到与起点最近的一点作为新的起点
  {
   if (book[j] == 0 && dis[j] < MIN)
   {
    MIN = dis[j];
    flag = j;
   }
  }
  book[flag] = 1;
  for (k = 1; k <= n; k++)
  {
   if (dis[k] > dis[flag] + map[flag][k]&&book[k]==0)
    dis[k] = dis[flag] + map[flag][k];
  }
 }
}
int main()
{
 int T, S, D, a, b, c;
 while (scanf("%d%d%d", &T, &S, &D) != EOF)
 {
  for(int i=0;i<1001;i++)
            book[i]=0;
  book[0] = 1;
  n = 0;
  for (int i = 0; i < 1001; i++)
  {
   for (int j = 0; j < 1001; j++)
    map[i][j] = inf;
   map[i][i] = 0;
  }
  while (T--)
  {
   scanf("%d%d%d", &a, &b, &c);
   n = max(max(n, a), b);
   if (c < map[a][b])
    map[a][b] = map[b][a] = c;
  }
  int MIN = inf;
  for (int i = 0; i < S; i++)
  {
   scanf("%d", &st[i]);
   map[0][st[i]] = map[st[i]][0] = 0;//家到这些城市的距离初始化为0
  }
  for(int i=0;i<=n;i++)
     dis[i]=map[0][i];
  for(int i=0;i<n;i++)
     scanf("%d",&en[i]);
  Dijkstra();
  for(int i=0;i<n;i++)
     MIN=min(MIN,dis[en[i]];
  printf("%d",MIN);
 }
 return 0;
}