blogeum
 
RSS-Symbol
Wenn Du über neue Weblog-Einträge Bescheid wissen möchtest, dann abonniere einfach den Atom-Feed oder folge mir bei Twitter.
✗

Algorithmus von Dijkstra

In der Informatik (speziell bei Datenstrukturen) stößt man bei kantengewichteten Graphen auf ein besonderes Problem: Wie findet man die günstigste (auch billigste) Verbindung zwischen einem Startknoten und allen anderen Knoten im Graphen?
Edsger W. Dijkstra, ein niederländischer Informatiker, beschrieb im Jahr 1959 einen Algorithmus, mit dessen Hilfe man die günstigsten Verbindungen in einem solchen Graphen finden kann. Einzige Voraussetzung ist, dass die Kantengewichte nicht negativ sein dürfen.

In der Vorlesungen Datenstrukturen hier an der TU bekamen wir die Aufgabe, diesen Algorithmus in C++ umzusetzen, unter der Voraussetzung, dass der Graph in Form einer Adjazenzmatix gegeben ist.
Um anderen Informatik-Studenten das Leben zu erleichtern, möchte ich im Folgenden meine Implementation veröffentlichen.

C++ Implementation des Dijkstra-Algorithmus

#include <iostream>

// Unendlich "definieren"
#define INF INT_MAX

// Anzahl an Knoten muss "hart" festgelegt werden
#define nodenum 9

class dijkstra {

public:
    void setMatrix(unsigned int matrix[nodenum][nodenum]);
    void setSource(unsigned int source);
    void calculate(bool step);
    void trace();

private:

    unsigned int matrix[nodenum][nodenum];
    unsigned int source;
    unsigned int distance[nodenum];            // Array für Entfernungen/Kosten
    unsigned int predecessor[nodenum];        // Array für Vorgängerknoten

};


void dijkstra::setSource(unsigned int source) {
    this->source = source;
}


void dijkstra::setMatrix(unsigned int matrix[nodenum][nodenum]) {
    memcpy(this->matrix, matrix, nodenum * nodenum * sizeof(unsigned int));
}


void dijkstra::calculate(bool step = false) {

    // Array für markierte Knoten
    bool marked[nodenum];

    // Initialisierung
    for(int x = 0; x < nodenum; ++x) {
        // Kein Knoten ist markiert
        marked[x] = false;

        // Kosten sind zunächst unendlich (INF = INT_MAX)
        this->distance[x] = INF;

        // Vorgänger sind nicht vorhanden
        this->predecessor[x] = 0;
    }
 
    // Startknoten besitzt Kosten 0
    this->distance[this->source] = 0;

    bool flag = true;

    while(flag) {
        // minimale Kosten initialisieren
        unsigned int minimum = INF;

        // zugehöriger (minimaler) Knoten
        int node = 0;

        // Minimale Distanz ermitteln
        for(int j = 0; j < nodenum; ++j) {
            // Knoten schon markiert -> überspringen (Zyklen vermeiden!)
            if(marked[j]) continue;

            // Distance kleiner als Minimum -> neues Minimum gefunden
            if(this->distance[j] < minimum) {
                minimum = this->distance[j];
                node = j;
            }
        }

        // Distanz aktualisieren, wenn Zielknoten über den gefundenen Minimumknoten billiger erreichbar
        for(int j = 0; j < nodenum; ++j) {
            if(!marked[j] && this->matrix[node][j] != 0 && this->distance[node] + this->matrix[node][j] < this->distance[j]) {
                this->distance[j] = this->distance[node] + this->matrix[node][j];
                this->predecessor[j] = node;
            }

            // jeden einzelnen Verbesserungsschritt ausgeben?
            if(step == true)
                (this->distance[j] == INF) ? printf("INF\t") : printf("%3d\t", this->distance[j]);
        }

        if(step == true)
            printf("\n\n");
        
        // gerade bestimmten Minimumknoten markieren
        marked[node] = true;

        // sind noch Knoten unmarkiert?
        flag = false;
        for(int j = 0; j < nodenum && !flag; ++j) {
            flag = !marked[j];
        }
    }
}


// Methode, die den günstigsten Weg vom angegebenen Startknoten zu den anderen Knoten aufzeigt
void dijkstra::trace() {

    for(int x = 0; x < nodenum; ++x) {
        // Wenn kein Vorgänger vorhanden und Knoten != Startknoten existiert keine Verbindung
        if(this->predecessor[x] == 0 && x != this->source) {
            printf("Keine Verbindung zwischen %d und %d gefunden\n\n", this->source, x);
            continue;
        }

        printf("G\x81nstigste Verbindung von %d nach %d\n", source, x);

        int j = x;

        // Vorgänger verfolgen bis zum Ziel ("Rückwärtssuche")
        while(this->predecessor[j] != 0) {
            printf("%d <- ", j);
            j = this->predecessor[j];
        }

        printf("%d\n\nKosten: %3d\n\n", j, this->distance[x]);
 }
}

// Beispielaufruf

void main() {

    unsigned int test[nodenum][nodenum] = {
        {   0,  15, INF, INF, INF, INF, INF, INF, INF },
        {  15,   0, INF,  30,  10, INF,  25,  10,  30 },
        { INF, INF,   0,  20, INF, INF,  15, INF, INF },
        { INF,  30,  20,   0, INF, INF, INF, INF, INF },
        { INF,  10, INF, INF,   0,  40,  10, INF, INF },
        { INF, INF, INF, INF,  40,   0,  20, INF, INF },
        { INF,  25,  15, INF,  10,  20,   0, INF, INF },
        { INF,  10, INF, INF, INF, INF, INF,   0,  10 },
        { INF,  30, INF, INF, INF, INF, INF,  10,   0 }
    };

    dijkstra *blubb = new dijkstra();

    // Matrix setzen
    blubb->setMatrix(test);

    // Startknoten setzen
    blubb->setSource(8);

    // Algorithmus ausführen
    blubb->calculate(true);

    // Günstigste Wege aufzeigen
    blubb->trace();

    system("Pause");
}

Der Code ist dokumentiert, sodass man ihn mit Vorkenntnis des Algorithmus’ verstehen sollte.

Anwendungen

Der beschriebene Algorithmus findet unter anderem bei Routenplanern Anwendung, wenn die kürzeste Verbindung zwischen zwei Orten gesucht werden soll. Die Orte und Zwischenstationen stellen die Knoten des Graphen dar, die Entfernungen dazwischen sind die Kantengewichte.

Beispielkarte von Deutschland

Ein andere Anwendung wäre beispielsweise ein Freundschaftsnetzwerk, in dem die Verbindungen einer Person zu deren Freunden und Freundesfreunden dargestellt werden soll, etwa in der Art „Wer kennt wen über wen?“

Weitere Informationen gibt’s im entsprechenden deutschen und englischen Wikipedia-Artikel.

Datum05. Juli 2009, am späten Nachmittag · Kommentare2 Kommentare · Schlagwörterc++, code, datenstrukturen, programmieren, studium

Icon von Del.icio.usIcon von diggIcon von FacebookIcon von reddit.comIcon von Stumble UponIcon von TechnoratiIcon von Twitter

Kommentare

  1. 30. Juli 2009, 13:31 UhrGravatarKommentar von VLC-Download

    Schöner Artikel!

  2. 06. Februar 2010, 22:36 UhrGravatarKommentar von Ibrahim

    gute arbeit.

 

Mitreden? Dann jetzt kommentieren!

Gestattete BBCode-Formatierungen sind [blockquote], [code], [em], [strong], [url].

* Pflichtfeld · E-Mail-Adresse ist nicht öffentlich sichtbar.

Was’n das?

blogeum ist das persönliche Weblog von Christian Gürtler – seines Zeichens begeisterter Webworker und Programmierer. Er studiert gegenwärtig Angewandte Informatik an der TU Chemnitz.

 

Abonnieren

RSS-IconImmer auf dem Laufenden mit den Einträgen aus dem Weblog als Atom-Feed. Nunmehr 72 Abonnenten!

Folge mir auf Twitter

 

Neue Kommentare

Christian: Hallo, interessante Funktion. Ich denke ich werde das Beispiel für JavaScript…

Tobias Neumann: Hallo, interessante Funktion. Ich denke ich werde das Beispiel für JavaScript…

Christian: OK, den Zugriff auf "superglobale" Objekte wie window habe ich nicht bedacht.…

ChrisB: Auf diese Weise haben wir auch JSON geparsed, aber ohne Sicherheitsbedenken.…

Martha: Das wundert mich auch. Rot ist doch eine Warnfarbe. Ich kann mir das auch nur…

 

Neue Einträge

 

Lesenswert

Werbung

Wikio - Top Blog - High-tech

 

© 2009–2010 Christian Gürtler

Die Blog-Inhalte stehen unter einer Creative Commons-Lizenz.

XHTML · CSS

BlogPingR.de - Blog Ping-Dienst, Blogmonitor Blogverzeichnis - Blog Verzeichnis bloggerei.de