首页 > 代码库 > ACM：最短路，dijkstra，邻接表的建立，使用邻接表跟优先队列的dijkstra，Bellman-Ford，Floyd。。

ACM：最短路，dijkstra，邻接表的建立，使用邻接表跟优先队列的dijkstra，Bellman-Ford，Floyd。。

2024-07-10 07:34:18   221人阅读

（一）dijkstra，邻接矩阵

所有边权均为正，不管有没有环，求单个源点出发，到所有节点的最短路。该方法同时适用于有向图和无向图。

#include <iostream>
#include <string>
#include <stack>
using namespace std;

const int MAXN = 1000;
const int INF = 100000000;
int n, m;
int maze[MAXN][MAXN], vis[MAXN], d[MAXN], fa[MAXN];  //d[i]表示节点i到源点0的距离

stack<int> s;
void print_path1(int j) {
	if(j == 0) return ;
	s.push(j);
	while(j) {
		for(int i = 0; i < n; ++i) {
			if(d[j] == d[i] + maze[i][j]) {
				s.push(i);
				j = i;
				break;
			}
		}
	}
	cout << s.top();
	s.pop();
	while(!s.empty()) {
		cout << "->" << s.top();
		s.pop();
	}
	cout << endl;
}

void print_path2(int j) {
	if(j == 0) return ;
	while(j) {
		s.push(j);
		j = fa[j];
	}
	s.push(j);
	cout << s.top();
	s.pop();
	while(!s.empty()) {
		cout << "->" << s.top();
		s.pop();
	}
	cout << endl;
}

int main() {
	freopen("E://data.txt", "r", stdin);
	cin >> n >> m;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			maze[i][j] = INF;
		}
	}
	for(int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		maze[u][v] = maze[v][u] = w;
	}
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i < n; ++i) d[i] = (i == 0 ? 0 : INF);  //初始化d数组
	for(int i = 0; i < n; ++i) {     //循环n次
		int m = INF, x;
		for(int y = 0; y < n; ++y) {     //在所有未标号的节点中，选出d值最小的节点x
			if(!vis[y] && d[y] <= m) m = d[x=y];
		}
		vis[x] = 1;
		for(int y = 0; y < n; ++y) {   //对于从x出发的所有边(x, y)，更新d[y] = min(d[y], d[x]+maze[x][y])
			if(d[y] > d[x] + maze[x][y]) {
				d[y] = d[x] + maze[x][y];
				fa[y] = x;   //维护父亲指针
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		cout << d[i] << endl;
		print_path1(i);  //打印路径方法1：从终点出发，不断顺着d[j] == d[i] + maze[i][j]的边(i, j)从节点j退回到节点i，直到回到起点。
		print_path2(i);  //打印路径方法2：空间换时间！在更新d数组的时候维护父亲指针！
	}
	return 0;
}

（二）邻接表的建立

邻接表既可以用于有向图也可以用于无向图，在这种表示方法中，每个节点i都有一个链表，里面保存着从i出发的所有边，对于无向图来说，每条边会在邻接表中出现两次。

我们这里用数组实现链表：首先给每条边编号，然后用first[u]保存节点u的第一条边的编号，next[e]表示编号为e的边的“下一条边”的编号。

下面的代码针对有向图，建立邻接表。

#include <iostream>
using namespace std;

const int MAXN = 1000;
int first[MAXN], next[MAXN], u[MAXN], v[MAXN], w[MAXN];

int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; ++i) first[i] = -1; 
	for(int e = 0; e < m; ++e) {
		cin >> u[e] >> v[e] >> w[e];
		next[e] = first[u[e]];
		first[u[e]] = e;
	}
	for(int i = 0; i < n; ++i) cout << first[i] << endl;
	for(int e = 0; e < m; ++e) cout << next[e] << endl;
	return 0;
}
上述代码的巧妙之处是插入到链表的首部而非尾部，这样就避免了对链表的遍历。在这里，同一个起点的各条边在邻接表中的顺序和读入顺序正好相反。

（三）使用邻接表跟优先队列的dijkstra。

queue跟priority_queue的唯一区别是，在优先队列中，元素并不是按照进入队列的先后顺序排列，而是按照优先级的高低顺序排列。pop()删除的是优先级最高的元素，而不一定是最先进入队列的元素。所以，获取对首元素的方法不再是front()，而是top()。

struct cmp{
	bool operator() (const int a, const int b) {  //a的优先级比b小时返回true
		return a % 10 > b % 10;
	}
};
priority_queue<int, vector<int>, cmp> q;  //“个位数大的优先级反而小”的整数优先队列


声明一个小整数先出队列的优先队列：

priority_queue< int, vector<int>, greater<int> > q;

在dijkstra算法中，不仅需要找出最小的d[i]，要连同这个节点的编号一起从优先队列中弹出来，所以我们用pair

为了方便起见，我们用typedef pair<int, int> pii自定义一个pii类型，则priority_queue< pii, vector<pii>, greater<pii> > q 就定义了一个由二元组构成的优先队列！

pair定义了它自己的排序规则——先比较第一维，相等时才比较第二维，因此需要按（d[i], i）而不是(i, d[i]) 的方式组合！


利用邻接表+二叉堆来实现dijkstra算法的代码如下：

#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 1000;
const int MAXM = 100000;
const int INF = 100000000;
int n, m;
int first[MAXN], d[MAXN], done[MAXN];   //在寻找距离源点最近的点x过程中，done[i]表示第i个节点已经被处理过
int u[MAXM], v[MAXM], w[MAXM], next[MAXM];
typedef pair<int, int> pii;

int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++) first[i] = -1;  //初始化邻接表的表头
	for(int e = 0; e < m; ++e) {     //邻接表的建立
		cin >> u[e] >> v[e] >> w[e];
		next[e] = first[u[e]];
		first[u[e]] = e;
	}
	priority_queue< pii, vector<pii>, greater<pii> > q;  //用于在所有未处理过的节点中，选出d值最小的节点x
	memset(done, 0, sizeof(done));  //一开始假设所有节点都没有被处理过
	q.push(make_pair(d[0], 0));   //起点进入优先队列
	for(int i = 0; i < n; ++i) d[i] = (i == 0 ? 0 : INF);
	while(!q.empty()) {
		pii u = q.top();
		q.pop();
		int x = u.second;   //x表示当前d值最小的节点的节点号
		if(done[x]) continue;    //已经算过，忽略
		done[x] = 1;
		for(int e = first[x]; e != -1; e = next[e]) {   //遍历从x出发的所有边（x,y）更新d[y]
			if(d[v[e]] > d[x] + w[e]) {
				d[v[e]] = d[x] + w[e];      //松弛成功，更新d[v[e]]
				q.push(make_pair(d[v[e]], v[e]));
			}
		}
	}
	for(int i = 0; i < n; ++i) cout << d[i] << endl; 
	return 0;
}

（四）Bellman-Ford算法

当图中有负权的时候，最短路就不一定存在了，但是还是可以在最短路存在的情况下把它求出来。

如果最短路存在，则该最短路一定不含环！

原因：分为正环，零环，负环三种情况考虑！

如果是正环或零环，那最短路肯定不经过它！如果是负环，那肯定就不存在最短路了！

既然最短路不含环，那么该最短路就最多只经过n-1个节点（起点不算），所以可以通过n-1轮松弛操作得到！

#include <iostream>
using namespace std;

const int MAXN = 1000;
const int INF = 100000000;
int n, m;
int d[MAXN], u[MAXN], v[MAXN], w[MAXN];

int main() {
	cin >> n >> m;
	for(int e = 0; e < m; ++e) {
		cin >> u[e] >> v[e] >> w[e];
	}
	for(int i = 0; i < n; ++i) d[i] = INF;
	d[0] = 0;
	for(int k = 0; k < n-1; ++k) {   //迭代n-1次
		for(int e = 0; e < m; ++e) {   //检查每条边
			int x = u[e];
			int y = v[e];
			if(d[x] < INF) d[y] = min(d[y], d[x] + w[e]);  //松弛操作
		}
	}
	for(int i = 0; i < n; ++i) cout << d[i] << endl;
	return 0;
}


用队列实现的话，效率会更高，像这样：

#include<iostream>
#include<string>
#include<queue>
using namespace std;

const int INF = 1000000000;
const int MAXN = 1000;
const int MAXM = 100000;

int n, m;
int first[MAXN], d[MAXN];
int u[MAXM], v[MAXM], w[MAXM], next[MAXM];

int main() {
	cin >> n >> m;
	for(int i = 0; i < n; ++i) first[i] = -1;
	for(int e = 0; e < m; ++e) {
		cin >> u[e] >> v[e] >> w[e];
		next[e] = first[u[e]];
		first[u[e]] = e;
	}
	queue<int> q;
	int inq[MAXN];
	for(int i = 0; i < n; ++i) d[i] = (i==0 ? 0 : INF);
	memset(inq, 0, sizeof(inq));
	q.push(0);
	while(!q.empty()) {
		int x = q.front(); q.pop();
		inq[x] = 0;    //标记x不在队列中
		for(int e = first[x]; e != -1; e = next[e]) if(d[v[e]] > d[x]+w[e]) {
			d[v[e]] = d[x] + w[e];
			if(!inq[v[e]]) {    //如果点v[e]不在队列中
				inq[v[e]] = 1;   //标记点v[e]在队列中
				q.push(v[e]);
			}
		}
	}	
	for(int i = 0; i < n; i++)	cout << d[i] << endl;
	return 0;
}

（五）Floyd算法

如果要求计算每两点之间的最短路：

#include <iostream>
using namespace std;

const int MAXN = 1000;
const int INF = 1000000;
int d[MAXN][MAXN];
int n;

int main() {
	cin >> n;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(i == j) d[i][j] = 0;
			else d[i][j] = INF;
		}
	}
	for(int k = 0; k < n; ++k) {
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < n; ++j) {
				if(d[i][j] < INF && d[k][j] < INF) d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			cout << d[i][j] << endl;
		}
	}
	return 0;
}


联系
我们