Module: Algorithme de Dijkstra


Problem

8/14

Algorithme de Dijkstra dans l'ensemble O(M logN) c : Start (C++)

Theory Click to read/hide

Puisque le comportement asymptotique de l'implémentation naïve de l'algorithme de Dijkstra est : \(O(n^2 + m)\), alors à mesure que le nombre de sommets augmente, la vitesse de travail devient insatisfaisante.
 Diverses structures de données peuvent être utilisées pour l'amélioration : tas de Fibonacci, ensembles set ou une file d'attente prioritairepriority_queue. 
Prenons un exemple avec set, par conséquent, l'asymptotique finale est : \(O(n log (m))\) , détails.

Problem

On vous donne un graphique pondéré orienté. Trouver la distance la plus courte entre un sommet donné et un autre.
 
Entrée
La première ligne contient trois nombres : N, M, S et F (1≤ N≤ 100, 1≤ S, F≤ N), où N – nombre de sommets du graphe, M – nombre de côtes,  S– sommet initial, et F – final. Dans les N lignes suivantes, entrez N nombres chacun, n'excédant pas 100, – matrice d'adjacence graphique, où -1 signifie qu'il n'y a pas d'arête entre les sommets et tout nombre non négatif – la présence d'une arête de poids donné. Des zéros sont écrits sur la diagonale principale de la matrice.
 
Sortie
Il est nécessaire d'afficher la distance souhaitée ou -1 s'il n'y a pas de chemin entre les sommets spécifiés.

Exemples
# Entrée Sortie
1 4 4 3 4
3 1 3
1 2 3
2 4 3
3 4 10 		9

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <set>
#include <vector>
using namespace std;

	const int INF = 1000000000;

	int main() {
		int n, m ,s, f;
		cin >> n>>m>>s>>f;
		
		vector < vector < pair<int, int> > > g(n+1);
		// чтение графа  
		vector<int> d(n+1, INF);
		d[s] = 0;
		set < pair<int, int> > q;
		q.insert(make_pair(d[s], s));
		while (!q.empty()) {
			int v = q.begin()->second;
			q.erase(q.begin());

			for (size_t j = 0; j < g[v].size(); ++j) {
				int to = g[v][j].first,
					len = g[v][j].second;
				if (d[v] + len < d[to]) {
					q.erase(make_pair(d[to], to));
					d[to] = d[v] + len;
					q.insert(make_pair(d[to], to));
				}
			}
		}

		if (d[f] == 10000000)
			cout << "-1";
		else
			cout << d[f];
	}

     

Program check result

To check the solution of the problem, you need to register or log in!