A Dijkstra-algoritmus egy gráfkeresési algoritmus, amely a legrövidebb út meghatározására szolgál egy súlyozott gráf adott kezdőcsúcsából az összes többi csúcsba. Az algoritmus csak nem negatív élű gráfok esetén működik korrekt módon.
Dijkstra(G, start):
Távolság = * G.csúcsok_száma
Távolság = 0
Látogatott = üres halmaz
Sor = PrioritásiSor()
Sorba helyez(start, 0)
amíg Sor nem üres:
(aktuális_csúcs, távolság) = Sorból kivesz()
ha aktuális_csúcs már látogatott:
folytatás
Látogatott.insert(aktuális_csúcs)
minden szomszéd S az aktuális_csúcs szomszédai közül:
új_távolság = távolság + él_súlya(aktuális_csúcs, S)
ha új_távolság < Távolság:
Távolság = új_távolság
Sorba helyez(S, új_távolság)
visszatér Távolság
import heapq
def dijkstra(graph, start):
# Távolságok és prioritási sor inicializálása
distances = {node: float('infinity') for node in graph}
distances = 0
priority_queue = # (távolság, csúcs)
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# Ha egy rövidebb út már ismert, folytassuk
if current_distance > distances:
continue
# Szomszédok bejárása
for neighbor, weight in graph.items():
distance = current_distance + weight
# Ha rövidebb utat találunk
if distance < distances:
distances = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# Példa gráf
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 6},
'C': {'A': 4, 'B': 2, 'D': 3},
'D': {'B': 6, 'C': 3}
}
print(dijkstra(graph, 'A')) # Kimenet: {'A': 0, 'B': 1, 'C': 3, 'D': 6}
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
using namespace std;
// Típus alias az élek reprezentációjához (távolság, csúcs)
typedef pair<int, int> Edge;
// Típus alias a gráf reprezentációjához (szomszédok és élsúlyok)
typedef unordered_map<int, unordered_map<int, int>> Graph;
// Dijkstra-algoritmus megvalósítása
vector<int> dijkstra(const Graph& graph, int start, int n) {
// Távolságvektor inicializálása "végtelen" értékekkel
vector<int> distances(n, numeric_limits<int>::max());
distances = 0; // A kezdőcsúcs távolsága 0
// Prioritási sor (minimum prioritási sor a távolságok alapján)
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
pq.push({0, start}); // A kezdőcsúcs hozzáadása távolság=0 értékkel
// Fő ciklus: amíg van feldolgozatlan csúcs a sorban
while (!pq.empty()) {
// Vegyük ki a legkisebb távolságú csúcsot
auto = pq.top();
pq.pop();
// Ha az aktuális távolság nagyobb, mint a már ismert, hagyjuk ki
if (current_distance > distances)
continue;
// Járjuk be az aktuális csúcs összes szomszédját
for (const auto& : graph.at(current_node)) {
// Számítsuk ki az új potenciális távolságot a szomszédhoz
int new_distance = current_distance + weight;
// Ha az új távolság kisebb, frissítsük, és adjuk hozzá a sorhoz
if (new_distance < distances) {
distances = new_distance;
pq.push({new_distance, neighbor});
}
}
}
// Adjunk vissza egy vektort, ami tartalmazza az összes csúcs távolságát a kezdőcsúcstól
return distances;
}
int main() {
// Súlyozott gráf definiálása szomszédsági lista reprezentációval
Graph graph = {
{0, {{1, 1}, {2, 4}}}, // 0. csúcs kapcsolatai: 1 (súly 1), 2 (súly 4)
{1, {{0, 1}, {2, 2}, {3, 6}}}, // 1. csúcs kapcsolatai: 0, 2, 3
{2, {{0, 4}, {1, 2}, {3, 3}}}, // 2. csúcs kapcsolatai: 0, 1, 3
{3, {{1, 6}, {2, 3}}} // 3. csúcs kapcsolatai: 1, 2
};
// Dijkstra-algoritmus meghívása a 0. csúcsból, 4 csúcsot tartalmazó gráfra
vector<int> distances = dijkstra(graph, 0, 4);
// Az eredmények kiíratása
for (int i = 0; i < distances.size(); ++i) {
cout << "Távolság a 0-tól a(z) " << i << "-ig: " << distances << endl;
}
return 0; // Program befejezése
}