Wikiszótár

Dijkstra-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈdijkʃtrɒɒlɡoritmuʃ]

Főnév

Dijkstra-algoritmus

  1. (matematika, gráfelmélet, algoritmusok) A Dijkstra-algoritmus egy mohó algoritmus, amivel irányított vagy irányítás nélküli gráfokban lehet megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva.

Dijkstra-algoritmus bemutatása

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.


Elmélet

Lépései:

  1. Kezdet:
    • Hozzunk létre egy távolságtömböt ((distance)), amely minden csúcs számára a legrövidebb ismert távolságot tárolja a kezdőcsúcstól. Kezdetben a kezdőcsúcs távolsága 0, a többi csúcsé pedig () (végtelen).
    • Tartsunk nyilván egy prioritási sort vagy minimum halmazt, amely a következő csúcs kiválasztására szolgál a feldolgozás során.
  2. Ismétlés:
    • Válasszuk ki a prioritási sorból azt a csúcsot, amelyhez a legkisebb távolság tartozik, és nevezzük ezt az aktuális csúcsnak.
    • Frissítsük az aktuális csúcs összes szomszédjának távolságát, ha a kezdőcsúcstól az aktuális csúcson keresztül rövidebb utat találunk.
  3. Vég:
    • Az algoritmus befejeződik, amikor minden csúcsot meglátogattunk, vagy a prioritási sor üres.

Fontos tulajdonságok:

  • Időkomplexitás:
    • Egyszerű megvalósítás esetén: (O(V^2)).
    • Prioritási sorral (pl. minimumkúppal): (O((V + E) V)), ahol (V) a csúcsok száma, (E) pedig az élek száma.
  • Térkomplexitás: (O(V + E)), a gráf és a távolságtömb tárolása miatt.


Pszeudokód

Dijkstra(G, start):
    Távolság = [végtelen] * G.csúcsok_száma
    Távolság[start] = 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[S]:
                Távolság[S] = új_távolság
                Sorba helyez(S, új_távolság)

    visszatér Távolság

Python implementáció

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[start] = 0
    priority_queue = [(0, start)]  # (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[current_node]:
            continue

        # Szomszédok bejárása
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # Ha rövidebb utat találunk
            if distance < distances[neighbor]:
                distances[neighbor] = 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}

C++ implementáció

#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[start] = 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 [current_distance, current_node] = pq.top();
        pq.pop();

        // Ha az aktuális távolság nagyobb, mint a már ismert, hagyjuk ki
        if (current_distance > distances[current_node])
            continue;

        // Járjuk be az aktuális csúcs összes szomszédját
        for (const auto& [neighbor, weight] : 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[neighbor]) {
                distances[neighbor] = 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[i] << endl;
    }

    return 0; // Program befejezése
}

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Dijkstra-algoritmus&oldid=3479439”