刚学最短路,这个写法是正确的吗
查看原帖
刚学最短路,这个写法是正确的吗
100014
Niko!楼主2020/7/16 18:07

例如我要求出 11 到剩下节点的最短路

struct cmp{
    bool operator() (int a,int b ){
        return dis[a] > dis[b];
	}
};

std::priority_queue<int,std::vector<int>, cmp>q;

void dijkspfa() {
	for (int i = 2; i <= n; ++ i) dis[i] = 1e17;
	q.push(1); inq[1] = 1;
	while (!q.empty()) {
		int u = q.top(); q.pop();
		for (int v:G[u]) {
			if (dis[v] > dis[u] + w(u,v)) {
				dis[v] = dis[u] + w(u,v);
				if (!inq[v]) { q.push(v); inq[v] = 1; }
			}
		}inq[u] = 0;
	}
}

简单来说就是,把 spfa 的 queue 换成 priority_queue,比较关键字为 dis[a] < dis[b]

首先这样做不符合 priority_queue 的规范,因为它不支持修改,而算法运行过程中是会修改 dis 的值的,也就是会破坏 priority_queue 的结构。也因此它不能保证弹出的是距离最短的节点,但是因为算法流程是 spfa,一个节点可以重复入队,因此不影响正确性。

这样做可以通过目前我已知的(虽然我并没有做几道)所有最短路题,因此想问这样做(的时间复杂度)是对的吗,如果不对能否叉掉?

前置约定:边权非负

2020/7/16 18:07
加载中...