図論学習ノート3

図論学習ノート3

Bellman−Fordアルゴリズム

緩和

負辺権操作

負権環判定

シンプル

を実現しました.

Spfa

思想

実現

Bellman-Fordアルゴリズム
Bellman−Fordアルゴリズム:D i j k s t r a Dijkstra Dijkstra同様に、緩和動作に基づいて、すなわち推定された最短経路値は、最適解が得られるまで徐々により正確な値に置換される.2つのアルゴリズムでは、計算時の各辺間の推定距離値は真実値よりも大きく、新たに見つけられた経路の最小長に置き換えられている.
締まりがない
各緩和動作は実際には隣接ノードへのアクセスであり,n番目の緩和動作は全ての深さがnである経路が最も短いことを保証する.図の最短経路が最も長いため、124 V 124−1辺を超えることはない.
エッジの権限を持って操作する
「たるみ」の操作は広さの上で道を探すので、マイナス側を操作して結果に影響しません.
負のループ判定
すべての辺を処理し終わった後に、もし緩むことができる辺があるならば、きっと負の権力の輪が存在します.
質素実現

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 505;

struct Node {
    int u, v, w;
} node[MAXN];

int n, m, s, t;
int dis[MAXN], pre[MAXN];

bool Bellman_Ford(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    pre[s] = 0;
    for (int i = 1; i < n; i++) {//   n - 1 
        for (int j = 1; j <= m; j++) {//      
            if (dis[node[j].u] + node[j].w < dis[node[j].v]) {//  
                dis[node[j].v] = dis[node[j].u] + node[j].w;
                pre[node[j].v] = node[j].u;
            }
        }
    }
    for (int i = 1; i <= m; i++) {//     
        if (dis[node[i].u] + node[i].w < dis[node[i].v]) {
            return false;
        }
    }
    return true;
}

void print(int x) {//    
    if (pre[x] == 0) {
        printf("%d ", x);
        return;
    }
    print(pre[x]);
    printf("%d ", x);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, ui, vi, wi; i <= m; i++) {
        scanf("%d %d %d", &ui, &vi, &wi);
        node[i].u = ui;
        node[i].v = vi;
        node[i].w = wi;
        pre[vi] = ui;
    }
    scanf("%d %d", &s, &t);
    if (Bellman_Ford(s, t)) {
        printf("%d
", dis[t]);
        print(t);
    } else {
        printf("No Solution
");
    }
    return 0;
}

Spfa
思想
隊列を作って、隊の頭のてっぺんを取ってuをつけます.点uに接続されたすべての点vを緩和し、見積もり値を更新できれば、点vをキューに入れないと、点vを列の中に入れます.もう列の中にいれば、使わないでください.サイクルはチームが空になるまで、単一ソースの一番短い解を完成しました.
実現する

int n, m, s, t;
int dis[MAXN];
bool vis[MAXN];

struct edge {//  
    int v, w;
    edge() {}
    edge(int V, int W) {
        v = V;
        w = W;
    }
};

vector<edge> G[MAXM];
queue<int> q;

void AddEdge(int u, int v, int w) {//  
    G[u].push_back(edge(v, w));
    G[v].push_back(edge(u, w));
}

void Spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while (q.size()) {
        int u = q.front();//    
        q.pop();
        vis[u] = 0;
        for (int i = 0; i < G[u].size(); i++) {
            if (dis[u] + G[u][i].w < dis[G[u][i].v]) {//     
                dis[G[u][i].v] = dis[u] + G[u][i].w;
                if (!vis[G[u][i].v]) {
                    vis[G[u][i].v] = 1;
                    q.push(G[u][i].v);
                }
            }
        }
    }
}