最短路问题

Feb 18, 2021

弗洛伊德算法

通过中间节点 k 来实现 i 和 j 的距离缩短，空间和时间复杂度都为 n3，一般数据在 400 以内可以使用。

for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++)
    for (int k = 0; k < n; k++)
      if (ai < inf && ak < inf)
      {
        if (ai + ak < ai)
        {
          ai = ai + ak;
        }
      }

迪杰斯特拉算法

指定一个点到其余各个顶点的最短路径，也叫“单源最短路径”。

矩阵存储边代码：

int e10, dis[10], book[10], n, m, t1, t2, t3, u, v, min;
int inf = 1 << 30;

//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d%d", &n, &m);

//初始化
for (int i = 1; i <= n; i++)
  for (int j = 1; j <= m; j++)
  {
    if (i == j)
      ei = 0;
    else
      ei = inf;
  }

//读入边
for (int i = 0; i < m; i++)
{
  scanf("%d%d%d", &t1, &t2, &t3);
  et1 = t3;
}

//初始化dis数组，这是1号顶点到其余各个顶点的初始化路程
for (int i = 1; i <= n; i++)
  dis[i] = e1;

//book数组初始化
for (int i = 1; i <= n; i++)
  book[i] = 0;
book[1] = 1;

//核心算法
for (int i = 1; i <= n - 1; i++)
{
  //找到离1号点最近的顶点
  min = inf;
  for (int j = 1; j <= n; j++)
    if (book[j] == 0 && dis[j] < min)
    {
      min = dis[j];
      u = j;
    }
  book[u] = 1;
  for (int v = 1; v <= n; v++)
    if (eu < min)
      if (dis[v] > dis[u] + eu)
        dis[v] = dis[u] + eu;
}

//输出结果
for (int i = 1; i <= n; i++)
  printf("%d ", dis[i]);

链式前向星存储边：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

struct EDGE
{
  int next; //下一条边的存储下标
  int to;   //这条边的终点
  int w;    //权值
};
EDGE edge[100];

int n, m, cnt;
int head[10]; //head[i]表示以i为起点的第一条边

void Add(int u, int v, int w)
{ //起点u, 终点v, 权值w
  edge[++cnt].next = head[u];
  edge[cnt].w = w;
  edge[cnt].to = v;
  head[u] = cnt; //第一条边为当前边
}
int main()
{
  int dis[10], book[10], t1, t2, t3, u, v, min;
  int inf = 1 << 30;

  //读入n和m，n表示顶点个数，m表示边的条数
  scanf("%d%d", &n, &m);

  //读入边
  for (int i = 0; i < m; i++)
  {
    scanf("%d%d%d", &t1, &t2, &t3);
    Add(t1, t2, t3);
  }

  //初始化dis数组，这是1号顶点到其余各个顶点的初始化路程
  for (int i = 1; i <= n; i++)
    dis[i] = inf;
  dis[1] = 0;
  for (int i = head[1]; i != 0; i = edge[i].next)
    dis[edge[i].to] = edge[i].w;

  //book数组初始化
  for (int i = 1; i <= n; i++)
    book[i] = 0;
  book[1] = 1;

  //核心算法
  for (int i = 1; i <= n - 1; i++)
  {
    //找到离1号点最近的顶点
    min = inf;
    for (int j = 1; j <= n; j++)
      if (book[j] == 0 && dis[j] < min)
      {
        min = dis[j];
        u = j;
      }

     book[u] = 1;
     for (int v = head[u]; v != 0; v = edge[v].next)
         if (dis[edge[v].to] > dis[u] + edge[v].w)
             dis[edge[v].to] = dis[u] + edge[v].w;
  }

  //输出结果
  for (int i = 1; i <= n; i++)
    printf("%d ", dis[i]);

  return 0;
}
/*
输入
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4

输出
0 1 8 4 13 17
*/

使用优先队列对算法进行优化：

#include <cstdio>
#include <cstring>
#include <queue>
#include <ctime>
using namespace std;
const int MAX_N = 30000, MAX_L = 30000; //边的最大数量

bool isPrint = 0;
int n, m;
int dis[MAX_N], book[MAX_N], nodeExist[MAX_N];

// 使用优先队列存结点，降低松弛操作复杂度
struct NODE
{
    int aimNode, distance;
    NODE(int aimNode, int distance) : aimNode(aimNode), distance(distance) {}
    bool operator<(const NODE &rhs) const
    {
        return distance > rhs.distance;
    }
};
priority_queue<NODE> Q;

// 链式前向星存边
struct EDGE
{
    int next; //下一条边的存储下标
    int to;        //这条边的终点
    int w;        //权值
};
EDGE edge[MAX_L];
int cnt;
int head[MAX_N]; //head[i]表示以i为起点的第一条边
void Add(int u, int v, int w)
{
    //起点u, 终点v, 权值w
    edge[++cnt].next = head[u];
    edge[cnt].w = 1;
    edge[cnt].to = v;
    head[u] = cnt; //第一条边为当前边
}

void Dijikstra(int startNode)
{
    memset(dis, 0x7F, sizeof(dis));
    memset(book, 0, sizeof(book));
    dis[startNode] = 0;
    book[startNode] = 1;

    //核心算法
    Q.push(NODE(startNode, 0));
    while (!Q.empty())
    {
        NODE q = Q.top();
        Q.pop();
        // book[q.aimNode] = 1;
        for (int v = head[q.aimNode]; v != 0; v = edge[v].next)
        {
            if (dis[edge[v].to] > dis[q.aimNode] + edge[v].w)
            {
                dis[edge[v].to] = dis[q.aimNode] + edge[v].w;
                Q.push(NODE(edge[v].to, dis[edge[v].to]));
            }
        }
    }

    //输出结果
    if (isPrint)
    {
        printf("---- Now Start Node IS %d ----\n", startNode);

        for (auto i = 0; i < MAX_N; i++)
            if (nodeExist[i])
            {
                if (dis[i] == 2139062143)
                    printf("%d->%d: inf\n", startNode, i);
                else
                    printf("%d->%d: %d\n", startNode, i, dis[i]);
            }
    }
}

int main()
{
    clock_t start, end;
    start = clock();

    FILE *fr, *fw;
    fr = freopen("small.txt", "r", stdin);
    if (isPrint)
        fw = freopen("out_small.txt", "w", stdout);

    //读入n和m，n表示顶点个数，m表示边的条数
    scanf("%d%d", &n, &m);

    //读入边
    for (int i = 0; i < m; i++)
    {
        int t1, t2;
        scanf("%d%d", &t1, &t2);
        nodeExist[t1] = nodeExist[t2] = 1;
        Add(t1, t2, 1);
    }

    // 求所有点为起点的单源最短路
    int p = 0;
    for (int i = 0; i < MAX_N; i++)
    {
        if (!nodeExist[i])
            continue;
        p++;
        if (!isPrint)
            printf("%d/%d\n", p, n);
        Dijikstra(i);
    }

    fclose(fr);
    if (isPrint)
        fclose(fw);
    end = clock();
    if (!isPrint)
        printf("%fs", double(end - start) / CLOCKS_PER_SEC);
    return 0;
}

bellman-ford 算法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
using namespace std;
const int MAX_L = 30000, MAX_N = 30000;
int dis[MAX_N], nodeExist[MAX_N], u[MAX_L], v[MAX_L], w[MAX_L];
int n, m;
bool isPrint = 0;
void bellmanFord(int origin)
{
    memset(dis, 0x7F, sizeof(dis));
    dis[origin] = 0;
    for (int i = 0; i < MAX_L; i++)
        if (u[i] == origin)
            dis[v[i]] = 1;

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= m; i++)
            if (dis[v[i]] > dis[u[i]] + w[i])
                dis[v[i]] = dis[u[i]] + w[i];

    if (isPrint)
    {
        printf("---- Now Start Node IS %d ----\n", origin);
        for (auto i = 0; i < MAX_N; i++)
            if (nodeExist[i])
            {
                if (dis[i] == 2139062143)
                    printf("%d->%d: inf\n", origin, i);
                else
                    printf("%d->%d: %d\n", origin, i, dis[i]);
            }
    }
}

int main()
{
    clock_t start, end;
    start = clock();
    FILE *fr, *fw;
    fr = freopen("small.txt", "r", stdin);
    if (isPrint)
        fw = freopen("out_small.txt", "w", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        nodeExist[v[i]] = nodeExist[u[i]] = w[i] = 1;
    }

    // 求所有点为起点的单源最短路
    int p = 0;
    for (int i = 0; i < MAX_N; i++)
        if (nodeExist[i])
        {
            p++;
            bellmanFord(i);
            if (!isPrint)
                printf("%d/%d\n", p, n);
        }

    fclose(fr);
    if (isPrint)
        fclose(fw);
    end = clock();
    if (!isPrint)
        printf("%fs", double(end - start) / CLOCKS_PER_SEC);
    return 0;
}

dis 数组作用与迪杰斯特拉算法相同。u、v、w 三个数组用来记录边的信息。

第 i 条边存储在 u[i] v[i] w[i]中，表示从顶点 u[i]到到顶点 v[i]的边权值为 w[i].

SPFA 算法

设立一个先进先出的队列 q 用来保存待优化的结点，优化时每次取出队首结点 u，并且用 u 点当前的最短路径估计值对离开 u 点所指向的结点 v 进行松弛操作，如果 v 点的最短路径估计值有所调整，且 v 点不在当前的队列中，就将 v 点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

dis[i] > dis[v] + a[v][i]

“>“改为”<“后可求最长路

代码示例：

void spfa(int s)
{
  for (int i = 0; i <= n; i++)
    dis[i] = 99999999; //初始化每点i到s的距离
  dis[s] = 0;
  vis[s] = 1;
  q.push(s); //队列初始化,s为起点,dis数组作用与bellman-ford算法相同
  int i, v;
  while (!q.empty())
  { //队列非空
    v = q.front();//取队首元素
    vis[v] = 0;//释放队首结点，因为这节点可能下次用来松弛其它节点，重新入队
    for (i = 0; i <= n; i++) //对所有顶点
      if (a[v][i] > 0 && dis[i] > dis[v] + a[v][i])
      { //节点s到节点i通过节点v松弛
        dis[i] = dis[v] + a[v][i]; //修改最短路
        if (vis[i] == 0)
        { //如果扩展结点i不在队列中，入队
          q.push(i);
          vis[i] = 1;
        }
      }
  }
}