「Note」图论学习笔记2

@TOC

多源最短路

Floyd

$Floyd$是基于$DP$思想。 设$k$为中转点，与$i$, $j$都有边相连。 那么可以得到$dis[i][j]$的最短路径的状态转移方程为： $dis[k,i,j]=min(dis[k-1,i,j], dis[k-1,i,k]+dis[k-1,k,j]$

memset(dis, 0x3f, sizeof(dis));
memset(pre, 0, sizeof(pre));
pre[u][v] = u;

void Floyd() {
	for(int k = 1;k <= n; k++) {
		for(int i = 1;i <= n; i++) {
			for(int j = 1;j <= n; j++) {
				if(dis[i][j] > dis[i][k] + dis[k][j]) {
					dis[i][j] = dis[i][k] + dis[k][j];
					pre[i][j] = pre[k][j];//输出路径
				}	
			}
		}
	}
}

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

Dijkstra

$Dijkstra$使用贪心思想，求最短路的步骤如下： 1.初始化：把$dis[]$置为∞，$v[]$置为0表示还没有访问过。 2.循环遍历与当前节点相邻的节点，找出最短的距离。 3.用找出的最短距离更新剩下的节点。 ##### 一般版本

void Dijkstra(int s, int t) {
	memset(dis, 0x3f, sizeof(dis));
	memset(v, 0, sizeof(v));
	v[s] = 1;
	for(int i = 1;i < n; i++) {
		int k = 0;
		for(int j = 1;j <= n; j++) {
			if(! v[j] && (k == 0 || dis[j] < dis[k])) k = j;
		}
		v[k] = 1;
		for(int j = 1;j <= n; j++) {
			if(dis[k] + w[k][j] < dis[j]) {
				dis[j] = dis[k] + w[k][j];
				pre[j] = k;
			}
		}
	}
}

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

邻接表优化

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

void DijkstraAdl(int s, int t) {
	memset(dis, 0x3f, sizeof(dis));
	memset(v, 0, sizeof(v));
	dis[s] = 0;
	for(int i = 1;i <= n; i++) {
		int u, v, w;
		for(int j = 1;j <= n; j++) {
			if(! v[i] && dis[i] < dis[u]) u = i;
		}
		v[u] = 1;
		for(int j = 0;j < G[u].size(); j++) {
			v = G[u][j].v, w = G[u][j].w;
			if(dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				pre[v] = u;
			}
		}
	}
}

优先队列优化

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2505;

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

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

struct node {
    int u, dis;
    node() {}
    node(int U, int D) {
        u = U;
        dis = D;
    }
    friend bool operator<(node x, node y) { return x.dis > y.dis; }
};

priority_queue<node> q;
vector<edge> G[MAXN];

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

void Dijkstra(int s, int t) {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push(node(s, 0));
    while (q.size()) {
        int now = q.top().u;
        q.pop();
        if (vis[now])
            continue;
        vis[now] = 1;
        for (int i = 0; i < G[now].size(); i++) {
            int v = G[now][i].v;
            if (dis[v] > dis[now] + G[now][i].w) {
                dis[v] = dis[now] + G[now][i].w;
                q.push(node(v, dis[v]));
            }
        }
    }
}

int main() {
    scanf("%d %d %d %d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        AddEdge(u, v, w);
    }
    Dijkstra(s, t);
    printf("%d\n", dis[t]);
    return 0;
}