Is Dijkstra's overrated????

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

Recently I got accepted on the Shortest Routes I problem from the CSES problemset using the Bellman-Ford algorithm. If you don't know what relaxation means in this context or what the pseudocode of the Bellman-Ford algorithm looks like you should study the algorithm before continuing the reading.

Here's my idea for solving the problem

Firstly, I applied the typical optimization when all the edge weights in the given graph are positive, which involves stopping the algorithm once no relaxation operation occurs during an iteration. After getting TLE in 6 cases I thought in a way of ordering the edges in order to take advantage of the latter optimization. Finally, I deleted multi-edges(storing just the lowest weight of the repeted edges) and in a very intuitive manner I run a BFS from the source( node 1 in this case) and I sorted the edges in the same order the BFS had visited them (including back edges). Surprisingly, It passed the tests!!!!

I'm wondering if someone could be so gentle of hacking my solution or explain me why it works. I don't know how to filter by name in the hacking page of the CSES website in a certain problem, however, you can find my submission if you go to the hacking tab in the Shortest Routes I problem and then sort by maximum runnung time, my submission shows up in the 4th page with a max runtime of 0.95 seconds with the username Victor_Luis123. Thanks in advance.

Комментарии (14)

Написать комментарий?

Victor_Luis123

11 месяцев назад, # |

Auto comment: topic has been updated by Victor_Luis123 (previous revision, new revision, compare).

→ Ответить

hulm

← Rev. 2 →

The time complexity of Bellman-Ford might be too big if we iterate over edges, again and again, multiple times. So, we can ask the question, when do we need to iterate it over and over again? The answer is simple, let's consider some path from the vertex s to the vertex t. Let's say that this path is the shortest for these two vertices. We need to iterate over all edges one more time, if there is some vertex x and the path (x -> t) will be considered before the path (s -> x). It is very familiar to this problem: CSES — Collecting Numbers. So, Bellman-Ford works slow, if there are lots of 'edge inversions'.

Your solution sorts the edges and the edges that are closer to the starting vertex will be considered first. So, 'edge inversions' will be eliminated after such rearranging. This is what I understood from your code. If I made some mistakes, I am sorry.

Also, This solution will work slow if we have edges with negative weights.

(s -> x) is the path from s to x.

dondurmawillwinioiin2025

11 месяцев назад, # ^ |

-23

ааа все все

lotusblume

+42

"Bad graph": Line of n-1 vertices (2, 3, ..., n) and edge weights of 1 between them. Then add an edge from 1 to every even node with weight 10^9. Then add an edge from 1 to 2 with weight 1.

Graph

Generator source code

#include <iostream>
#include <vector>

struct Edge {
	int from, to, cap;
	Edge(int f, int t, int c) : from(f), to(t), cap(c) {}
};

int main() {
	int n = 100000;
	int m = 200000;
	const int INF = 1000000000;

	std::vector<Edge> edges;

	edges.emplace_back(1, 2, 1);

	for (int i = 4; i <= n && (int) edges.size() + 3 <= m; i += 2) {
		edges.emplace_back(i - 2, i - 1, 1);
		edges.emplace_back(i - 1, i, 1);
		edges.emplace_back(1, i, INF);
	}

	std::cout << n << ' ' << (int) edges.size() << '\n';

	for (const Edge& e : edges) {
		std::cout << e.from << ' ' << e.to << ' ' << e.cap << '\n';
	}

	return 0;
}

Your code needs 8 seconds on my computer to solve this graph.

+14

Well, Im still waiting for the response in my computer. Thanks a lot

mraron

+49

A few users were hacked: https://i.imgur.com/J8AD55f.png

Thank you so much

wery0

+11

There is an improvement for Bellman-Ford algorithm called SPFA (shortest path faster algorithm), aka Bellman-Ford with queue. It maintains the queue of nodes, takes node $$$v$$$ from the front, tries to improve distances to it's neighbours $$$v \Rightarrow h$$$, and if it succeeded, adds $$$h$$$ to the end of the queue if it wasn't in it. With the heuristic of swapping several first and last nodes in queue (check MAGIC stuff in my code), it passes the tests in $$$0.17s$$$.

Code.

Thank you, I have learned something new. And by the way, I really like your way of implementing in C++.

+34

Bad graph for SPFA: Line of n-1 vertices (2, 3, ..., n) and edge weights of 1 between them. Then add an edge from 1 to every node i with weight 2i. (Add the edges with larger weights first).

#include <algorithm>
#include <iostream>
#include <vector>

struct Edge {
	int from, to, weight;
	Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

int main() {
	int n = 100000;
	int m = 200000;

	std::vector<Edge> edges;

	for (int i = 2; i <= n && (int) edges.size() + 2 <= m; ++i) {
		edges.emplace_back(i - 1, i, 1);
		edges.emplace_back(1, i, 2 * i);
	}

	std::reverse(edges.begin(), edges.end());

	std::cout << n << ' ' << (int) edges.size() << '\n';

	for (const Edge& e : edges) {
		std::cout << e.from << ' ' << e.to << ' ' << e.weight << '\n';
	}

	return 0;
}

Your code needs 12 seconds on my computer to solve this graph. Your code without "MAGIC" needs 45 seconds on my computer to solve this graph.

← Rev. 3 →

+13

I have submitted a solution using the SPFA algorithm and it got hacked in CSES with your testcases. Thanks for providing it.

+16

Added sorting of edges in non-decreasing order of weights — passed all tests in $$$0.18s$$$.

$$$ $$$

Meme

Split the edges into two edges to force the bad order:

Generator

#include <iostream>
#include <vector>

struct Edge {
	int from, to, weight;
	Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

int main() {
	int n = 100000;
	int m = 200000;

	std::vector<Edge> edges;

	edges.emplace_back(1, 2, n - 1);
	edges.emplace_back(2, 3, 1);

	for (int i = 5; i <= n && (int) edges.size() + 3 <= m; i += 2) {
		edges.emplace_back(i - 2, i, 1);
		edges.emplace_back(1, i - 1, n - (i / 2));
		edges.emplace_back(i - 1, i, 3 * (i / 2) - 2);
	}

	std::cout << n << ' ' << (int) edges.size() << '\n';

	for (const Edge& e : edges) {
		std::cout << e.from << ' ' << e.to << ' ' << e.weight << '\n';
	}

	return 0;
}

Your code needs 3 seconds.

Shuffle edges instead of sorting — $$$0.17s$$$ and your case works fast.

Блог пользователя Victor_Luis123

Here's my idea for solving the problem