超级简单易懂的Bellman-Ford算法 实现最短路径的问题

超级简单易懂的Bellman-Ford算法 实现最短路径的问题

最短路径是指连接图中两个顶点的路径中，所有边构成的权值之和最小的路径。之前提到的广度优先遍历图结构，其实也是一种计算最短路径的方式，只不过广度遍历中，边的长度都为单位长度，所以路径中经过的顶点的个数即为权值的大小。

最短路径中不能包含负权回路，因为每次经过负权回路，路径的权值会减少，所以这种情况下不存在最短路径。有些图结构中会存在负权边，用于表达通过某条途径可以降低总消耗，在有向图中，负权边不一定会形成负权回路，所以在一些计算最短路径算法中，负权边也可以计算出最短路径；在无向图中，负权边就意味着负权回路，所以无向图中不能存在负权边。后续的所有讨论都设定图中不存在负权回路的情况。

实验代码如下很容易读懂！

在这里插入代码片
#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include<queue>
using namespace std;
const int maxnum = 100;
const int maxint = 99999;
int a[2][10] = {0};
// 边，

//直接使用bellman ford实现最短路径的问题。

typedef struct Edge {
    int u, v;    // 起点，终点
    int weight;  // 边的权值
}Edge;


Edge edge[maxnum];     // 保存边的值

int  dist[maxnum];     // 结点到源点最小距离

int nodenum, edgenum, source;    // 结点数，边数，源点
// 初始化图
void init()
{
    
    // 输入结点数，边数，源点
    cin >> nodenum >> edgenum >> source;
    for (int i = 1; i <= nodenum; ++i)
    {
        dist[i] = maxint;
    }
        
    dist[source] = 0;
    for (int i = 1; i <= edgenum; ++i)
    {
        cin >> edge[i].u >> edge[i].v >> edge[i].weight;
        if (edge[i].u == source)          //注意这里设置初始情况
        {
            dist[edge[i].v] = edge[i].weight;
            a[0][source] = source;
        }
            if(a[0][edge[i].v]==0)
        a[0][edge[i].v] = edge[i].u;
    }
}

void relax(int u, int v, int weight)  // 松弛计算
{
    if (dist[v] > dist[u] + weight)
    {   dist[v] = dist[u] + weight;
        a[0][v] =u;
    }      
}

bool Bellman_Ford()
{
    for (int i = 1; i <= nodenum - 1; ++i)
        for (int j = 1; j <= edgenum; ++j)
            relax(edge[j].u, edge[j].v, edge[j].weight);
    bool flag = 1;
    for (int i = 1; i <= edgenum; ++i)// 判断是否有负环路
        if (dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
        {flag = 0;break;}    
    return flag;
}

int main()
{
   init();
   cout << "到达各节点最小权重：" << endl;
    if (Bellman_Ford())
        for (int i = 1; i<=nodenum; i++)
            cout << dist[i] << endl;
    cout << "最短路径如下："<<endl;
   for (int i = 1; i <= nodenum; i++)
    {
           a[1][i] = i;
           cout << a[0][i] <<"->"<< a[1][i]<<endl;
    }
   //测试数据如下//节点数 边数  起始点
  /*   5 10 1     
       1 2 6
       1 3 7
       2 4 5
       2 5 - 4
       2 3 8
       3 4 - 3
       3 5 9
       4 2 - 2
       5 1 2
       5 4 7    */
}