4. Der Dijkstra Algorithmus

Der Dijkstra Algorithmus

  • V

    ich versuche gerade den Dijkstra Algorithmus stur auszuführen - nur habe ich da noch etwas Verständnisprobleme

    Zu finden ist das ganze unter:
    http://gdz-srv3.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D196313

    ich will den kürzersten Weg in einem zusammenhängend Graphen ermitteln mithilfe des Algorithmus (Problem 2 was Dijkstra beschreibt)

    Dijkstra teilt die Kanten in drei Mengen ein:

    I. the branches occurring in the minimal paths from node P to the nodes in set A;

    Die Kanten die als Bestandteil der kürzesten Wege vom Knoten P zu den Konten aus der Menge A vorkommen - hab ich das richtig aufgefasst?

    II. the branches from which the next branch to be placed in set I will be selected; one and only one branch of this set will lead to each node in set B;

    Kanten, aus welchen die nächste Kante ausgwählt werden soll, die in der Menge I plaziert werden soll - eine und nur eine Kante aus dieser Menge führt zu jedem Knoten in der Menge B?
    ODER
    Menge der auswählbaren Kanten, aus der als nächstes eine Kante zur Menge I hinzugefügt wird. Nur ein einzige Kante aus dieser Menge führt zu jedem Knoten in der Menge B?

    hat dieses "plazieren" einen tieferen Sinn?

    0
  • B

    du fängst einfach am startpunkt an und nimmst immer den nächst kürzeren weg, durch den kein kreis entsteht. wenn alles verbunden ist hast du einen minimalen spannbaum.

    http://www.manderby.com/informatik/algodat/dijkstra.php

    0
  • V

    die Seite hilft mir nicht so recht weiter - ich habe da Problem mit dem Transfer - ich möchte mich hier strikt an den Artikel von Dikstra halten

    der anfang geht so:

    Am Anfang sind alle Knoten in der Menge C und alle Zweige in der Menge III. Als erstes wird der Knoten P (Ausgangsknoten) zur Menge A hinzugefügt

    ich werde heute mal noch einen Graphen zeichen und den Link hier posten, dann kann ich mal an einem konkretten Beispiel den Algorithmus durchspielen und jemand kann mir vielleicht meine Fehler sagen

    0
  • V

    bisher habe ich es so verstanden:

    http://turing.fh-landshut.de/~jamann/Dijkstra.pdf

    0
  • B

    ich hab keine ahnung wie das mit den mengen gemeint ist 😞
    der algorithmus ist aber total einfach.
    hier http://www.mcgods.de/fun/1904/node8.html ist er bebildert, vielleicht hilft dir das?

    0
  • J

    Klingt doch eigentlich recht einleuchtend mit den 3 Mengen. Und eigentlich seid ihr Euch auch einig. 🙂

    borg fängt beim Startpunkt an. Dijkstra nimmt ale Menge der Knoten wo er die kürzesten Wege hin schon kennt nur den Startknoten. Jetzt sagt Borg: Nimm den nächsten Knoten dazu, den Du noch nicht hast und den Du von einem bekannten Knoten auf kürzestem Weg erreichst.

    Dijkstra sagt: Es gibt noch zwei weitere Knotenmengen die, die man von den bekannten Knoten aus erreichen kann (und zuvor noch nicht erreicht hat) und die, die mit einem Schritt noch nicht zu erreichen sind.

    Diese Menge beschreibt die Einschränkung von borg: "den Du noch nicht hast und den Du von einem bekannten Knoten ... erreichst". Dijkstra wählt dann auch genau den, der davon am schnellsten zu erreichen ist.

    Danach müssen natürlich die Mengen upgedated werden. Der erreichte Knoten wird in die Menge der bekannten umgeordnet, die neu erreichbaren Knoten müssen jetzt in die Menge der erreichbaren etc.

    MFG Jester

    0
  • G
     

    #include <map>
#include <string>
#include <utility>
#include <functional>
#include <queue>
#include <vector>
#include <iostream>

typedef std::string Nodelabel;
typedef std::map<Nodelabel, int> Nodelist;
typedef std::map<Nodelabel, Nodelist> Graph;
typedef std::pair<Nodelabel, Nodelist> Node;
typedef std::pair<int, Nodelabel> Edg;

bool operator>(const Edg r, const Edg k){ return r.first>k.first; }

void dijkstra(Graph &graph, Nodelabel source, Nodelist &distance){
  distance.clear();
  std::priority_queue<Edg, std::vector<Edg>, std::greater<Edg> > que;
  que.push(Edg(0, source));

  while(!que.empty()){
    Edg tmped=que.top();
    Nodelabel tmpnl=tmped.second;
    que.pop();
    if(distance.count(tmpnl)==0){
      int dist=tmped.first;
      distance[tmpnl]=dist;
      Nodelist tempgraph=graph[tmpnl];
      Nodelist::iterator it;
      for(it=tempgraph.begin(); it!=tempgraph.end(); ++it){
        int distint=it->second;
        Nodelabel distlabel=it->first;
        que.push(Edg(dist+distint, distlabel));
      }
    }
  }
}

int main(){
  Graph test;
  test["japan"]["usa"]=12;
  test["usa"]["kanada"]=14;
  test["usa"]["kuba"]=3;
  test["kuba"]["kanada"]=4;

  Nodelist strecke;

  dijkstra(test, "japan", strecke);

  Nodelist::iterator it;
  for(it=strecke.begin(); it!=strecke.end(); ++it){
    std::cout<<it->second<<" <=> "<<it->first<<std::endl;
  }
  return 1;
}

    Ausgabe:

    20 <=> australien
27 <=> europa
0 <=> japan
19 <=> kanada
15 <=> kuba
12 <=> usa

    Es berechnet von startknoten zu jedem knoten den kw.
    Wie es nur von start zu ziehl sucht, habe ich noch nicht geschaft.
    Vieleicht hilfst dir was.

    MFG Ghost

    0
Anmelden zum Antworten