bellman ford 算法求最短路径

1 #include 
     
       2 using namespace std; 3 const int maxnum = 100; 4 const int maxint = 99999; 5  6 // 边， 7 typedef struct Edge{ 8     int u, v;    // 起点，重点 9     int weight;  // 边的权值10 }Edge;11 12 Edge edge[maxnum];     // 保存边的值13 int  dist[maxnum];     // 结点到源点最小距离14 15 int nodenum, edgenum, source;    // 结点数，边数，源点16 17 // 初始化图18 void init()19 {20     // 输入结点数，边数，源点21     cin >> nodenum >> edgenum >> source;22     for (int i = 1; i <= nodenum; ++i)23         dist[i] = maxint;24     dist[source] = 0;25     for (int i = 1; i <= edgenum; ++i)26     {27         cin >> edge[i].u >> edge[i].v >> edge[i].weight;28         if (edge[i].u == source)          //注意这里设置初始情况29             dist[edge[i].v] = edge[i].weight;30     }31 }32 33 // 松弛计算34 void relax(int u, int v, int weight)35 {36     if (dist[v] > dist[u] + weight)37         dist[v] = dist[u] + weight;38 }39 40 bool Bellman_Ford()41 {42     for (int i = 1; i <= nodenum - 1; ++i)43     for (int j = 1; j <= edgenum; ++j)44         relax(edge[j].u, edge[j].v, edge[j].weight);45     bool flag = 1;46     // 判断是否有负环路47     for (int i = 1; i <= edgenum; ++i)48     if (dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)49     {50         flag = 0;51         break;52     }53     return flag;54 }55 int main()56 {57     //freopen("input3.txt", "r", stdin);58     init();59     if (Bellman_Ford())60     for (int i = 1; i <= nodenum; i++)61         cout << dist[i] << endl;62     return 0;63 }