[数据结构与算法]最短路径问题

Floyd算法代码(邻接矩阵)

Floyd 算法复杂度高(结点数n < 200 可以考虑)，低效，但代码很简单，并且能求出任意两点之间的最短距离,还可以处理 有负权边的图。

代码中有一个有趣的地方，就是节点到自己的距离graph[i][i]并没有设初值为 0，graph[i][i]的值得要绕一圈才能求出，这一点可用于判断负圈。

负圈是这样产生的:

????????如果某些边的权值为负数，那么图中可能有这样的环路，环路上边的权值之和为负数，这样的环路就是负圈。每走一次这个负圈，总权值就会更小，导致陷在这个圈里出不来。

Floyd

用到了动态规划的思想，求两点之间的最短距离，可以分成两种情况考虑，即经过图中的某个点 K 的路径和不经过点 K 的路径，取两者中的最短路径。

?代码如下：

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e6;
const int NUM = 105;
int graph[NUM][NUM];
int n, m;
void floyd(){
    int s = 1;
    // n个中间点，每一个都考虑选与不选
    for (int k = 1; k <= n;++k)
        for (int i = 1; i <= n;++i)
            // 如果 i-->k 不通，那 i-->k-->j 肯定也不通
            if(graph[i][k]!=INF)
                for (int j = 1; j <= n;++j){
                    if(graph[i][j]>graph[i][k]+graph[k][j])
                        graph[i][j] = graph[i][k] + graph[k][j];
                }
    // 当 k = 2 时，有用到 k = 1 时计算出的graph[i][j] ， k>2 也是如此。 
}
int main(){
    while(~scanf("%d %d",&n,&m)){
        if(n==0&&m==0)
            return 0;
        for (int i = 1; i <= n;++i)
            for (int j = 1; j <= n;++j)
                graph[i][j] = INF;

        while(m--){
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            graph[a][b] = graph[b][a] = c;
        }
        floyd();

        /*
        cout<<graph[i][j]<<endl;
        即是 i-->j 的最短路径长度。
         */
    }
    system("pause");
    return 0;
}

SPFA算法代码(链式前向星)

解决单源点最短路径问题，给定一个起点，求它到图中所有n个结点的最短路径。

Bellman-Ford 算法的特点是只对相邻结点进行计算。

而 SPFA 是利用队列对 Bellman-Ford 进行优化的方法。

?代码如下：

#include<bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 10;
const int NUM = 1e6 + 5;
struct Edge{
    int to, next, w;
} edge[NUM];
int n, m, cnt;
int head[NUM];
int dis[NUM]; //记录所有结点到起点的距离
bool inq[NUM]; //inq[i] = true 表示节点 i 在队列中
int Neg[NUM]; //判断负圈
int pre[NUM]; //记录前驱结点
// 打印 s-->t 最短距离路径
void print_path(int s, int t){
    if(s==t){
        printf("%d ", s);
        return;
    }
    print_path(s, pre[t]);
    printf("%d ", t);
}

void init(){
    for (int i = 0; i <= NUM;++i){
        edge[i].next = -1;
        head[i] = -1;
    }
    cnt = 0;
}
// 前向星存图(很重要！)
void addedge(int u, int v, int w){
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++; 
}
// s : 起点
int spfa(int s){
    memset(Neg, 0, sizeof(Neg));
    memset(dis, INF, sizeof(dis));
    memset(inq, false, sizeof(inq));
    Neg[s] = 1;
    dis[s] = 0;
    queue<int> Q;
    Q.push(s);
    inq[s] = true;
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        inq[u] = false;
        // i 表示 边的编号
        for (int i = head[u]; i != -1;i = edge[i].next){
            int v = edge[i].to;
            int w = edge[i].w;
            // u 的第i个邻居v，它借道u，到s更进
            if(dis[v]>dis[u]+w){
                dis[v] = dis[u] + w;
                pre[v] = u;
                if(!inq[v]){
                    // 邻居v更新状态了，但是它不在队列中，把它放进队列中
                    inq[v] = true;
                    Q.push(v);
                    Neg[v]++;
                    // 出现负圈
                    if(Neg[v]>n){
                        return 1;
                    }
                }
            }
        }
    }
    printf("%d\n", dis[n]); // s-->n 的最短距离
    // s-->n 的最短路径
    print_path(s, n);
    return 0;
}
int main(){
    while(~scanf("%d %d", &n, &m)&&(n||m)){
        init();
        while(m--){
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        spfa(1); // 起点是 1 
    }
    system("pause");
    return 0;
}