最短路径 bellman-ford

初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0
迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次，看下面的描述性证明(当做树)）

检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在d[v]中

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 0x3f3f3f3f

#define N 1010

int nodenum, edgenum, original; //点，边，起点

typedef struct Edge //边

{

  int u, v;

  int cost;

}Edge;

Edge edge[N];

int dis[N], pre[N];

bool Bellman_Ford()

{

  for(int i = 1; i <= nodenum; ++i) //初始化

    dis[i] = (i == original ? 0 : MAX);

  for(int i = 1; i <= nodenum - 1; ++i)

    for(int j = 1; j <= edgenum; ++j)

      if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）

      {

        dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;

        pre[edge[j].v] = edge[j].u;

      }

      bool flag = 1; //判断是否含有负权回路

      for(int i = 1; i <= edgenum; ++i)

        if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)

        {

          flag = 0;

          break;

        }

        return flag;

}

void print_path(int root) //打印最短路的路径（反向）

{

  while(root != pre[root]) //前驱

  {

    printf("%d-->", root);

    root = pre[root];

  }

  if(root == pre[root])

    printf("%d\n", root);

}

int main()

{

  scanf("%d%d%d", &nodenum, &edgenum, &original);

  pre[original] = original;

  for(int i = 1; i <= edgenum; ++i)

  {

    scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);

  }

  if(Bellman_Ford())

    for(int i = 1; i <= nodenum; ++i) //每个点最短路

    {

      printf("%d\n", dis[i]);

      printf("Path:");

      print_path(i);

    }

  else

    printf("have negative circle\n");

  return 0;

}

秒客网

最短路径 bellman-ford

相关文章