Kürzester Weg in DAG finden?

Aufgabe:

Ich muss auf diesem DAG den unteren Algorithmus ausführen, weiß jedoch nicht, wie ich weiter vorgehen soll.

In einem Youtube Video kam mir der Algorithmus sehr simpel vor, aber die Formulierung unten lässt mich zweifeln, dass es das gleiche Verfahren ist wie im Video.

Ich habe den ersten Schritt, also die topologische Sortierung gemacht und bin auf "v1, v0, v6, v2, v7, v4, v3, v5" gekommen. Jetzt soll ich "s = 0" setzen und die restlichen Knoten auf ∞. soweit ich verstanden habe. Im Video (https://www.youtube.com/watch?v=TXkDpqjDMHA) müsste ich jetzt einfach den Graph durchgehen und jedes mal, wenn möglich, den kürzesten Pfad aktualisieren, bis ich für jeden Knoten den kürzesten Pfad vom Startknoten aus gefunden habe.Was da unten jedoch im Algorithmus steht, weiß ich nicht.

Bild zum Beitrag

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet

Destranix

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

IT, Informatik, Informatik

24.05.2024, 10:19

Im Grunde machst du zwei Durchläufe durch dne Graphen von Anfang bis Ende. (Da der Graph azyklisch ist und gerichtet gibt es auch Anfänge und Enden, evtl. zwar mehrere, aber das macht es kaum schwerer.)

Beim ersten Durchlauf sortierst du die Knoten topologisch. Das heißt, dass für jeden Knoten alle seine Nachfolger in der Sortierung danach kommen.
Das schaust du dir am besten einmal an ein paar Beispielen an, dann wird offensichtlich, was das bedeutet.
Der Graph ist dann so sortiert, dass erst alle Vorgänger eines Knoten drankommen, bevor der Knoten selbst an der Reihe ist.

Beim zweiten Durchlauf gehst du dann alle Knoten der Reihe nach durch. Durch die Sortierung arbeitest du erst alle Vorgänger eines Knotens ab, bevor du den Knoten selbst behandelst.
Dadurch kannst du für einen Knoten die jeweiligen Kosten berechnen, indem du die bereits berechneten Kosten aller Vorgänger plus die Kantengewichte vergleichst.

Die topologische Sortierung funktioniert folgendermaßen:
Für jeden Knoten bestimmst du die Menge der noch nicht abgearbeiteten Vorgängerknoten. Ist diese 0, fügst du den Knoten als nächstes Element in der Sortierung hinzu und verringerst die Zahl der noch nicht abgearbeiteten Vorgängerknoten für alle Nachfolger um 1.

Hallo, ich versuche gerade den Fifo Algorithmus zu verstehen aber im Internet findet man dazu nur etwas in Bezug zu Kostenrechnung. Bei mir geht es aber um Operations Research und um Graphen. Weiß jemand was die Schritte sind um den kürzesten Weg von einem Knoten zum anderen Knoten anhand des Fifo Algorithmus zu berechnen? Vielen dank

...zur Frage

Java Binärbaum mit Algorithmus erstellen?

Hallo, ich möchte für ein Projekt einen Binärbaum erstellen, der eine bestimmte Ordnung hat:

Ich habe zum Beispiel folgenden Input:
String pfad = "..-.-";

Und dann soll ein neuer Teilbaum bei der Stelle erstellt werden, die im String steht:

for(int i=0;i<pfad.length();i++ {
  if(pfad.charAt(i) == '.' {
    <Gehe einemal nach links>  
  }else {
    <Gehe einemal nach rechts>
  }
}

Ich habe mir gedacht, dass ich mit dem ersten Level beginne und dann immer weiter nach unten gehe. Der Teilbaum bei "..-." sollte also schon da sein, wenn der Pfad "..-.-" aufgerufen wird. Mein Problem ist, dass ich die Teilbäume nur nacheinander erstellen kann, z.B:

wurzel.getLeftTree().getRightTree().setLeftTree(<Content>)

aber wie man den Baum mit einen Algorithmus erstellen kann, weiß ich leider nicht. Ich hoffe mir kann jemand weiterhelfen.

...zur Frage

Welcher dieser Graphen besitzt einen Hamiltonkreis?

Kann mir jemand sagen welcher dieser Graphen ein Hamiltonkreis ist ?

...zur Frage

Dijkstra: Aufgabe richtig verstanden?

Ich sitze gerade an einer Aufgabe und bin total verwirrt was überhaupt die Aufgabe ist: Hier ist die Aufgabe

So wie ich das verstanden habe, soll ich die größte Kante im günstigsten Pfad finden. Ist das richtig? Wenn ich mir die Musterlösung anschaue scheint es, dass nach der kleinsten Kante im teuersten Pfad gefragt wird. Ich bin verwirrt und würde mich über Aufklärung sehr freuen

Gruß

...zur Frage

Höhe/Tiefe von Bäumen Infromatik?

ich hab auf Wikipedia gelesen, das bei Bäumen man mit der Definition der Höhe spielen kann. In den Folien meines Professor steht, dass die Höhe die Tiefe +1 ist.
D.h. ein nur eine Wurzel hat die Höhe 1. Und ein leerer die Höhe 0. auf Wikipedia hingegen steht ebenfalls, dass einige Autoren die Höhe mit der maximalen Tiefe gleich setzen.

Ich würde gern wissen, welchen Vorteil, das eine dem anderen gegenüber hat. Denn auf Wikipedia hab ich das nicht ganz verstanden , wäre nett, wenn’s einer kurz und einfacher erklären könnte beziehungsweise ganz simpel

...zur Frage

Beispiele für ungewichtete/gewichtete Graphen?

Hallo,

kann mir jemand Beispiele für ungewichtete und gewichtete Graphen bitte nennen (wo man sie in der Realität einsetzten könnte)?

Mit freundlichen Grüßen

...zur Frage

Zeige: Es ist nicht möglich, einen Springer auf einem 4 × 4-Schachbrett so zu ziehen, dass jedes Feld genau einmal besucht wird.?

Hey ich verzweifle gerade wirklich an dieser Beweisaufgabe,es handelt sich dabei nicht um das klassische Springerproblem und wir befinden uns im Rahmen der Graphentheorie,wenn ihr aber andere Beweise (vllt kombinatorischer Art oder so) habt immer her damit, weil ich komm wirklich nicht darauf und verboten ist es ja nicht,etwas auf andere Art zu beweisen, als es erwartet wird.

...zur Frage

Kann mir jemand einen konkreten Beispiel nennen, für wo man den shortest-Path und minimal spanning tree anwenden könnte?

Hallo Leute!

Ich wollte kurz fragen ob jemand einen Vorschlag hat, für wo man in der Realität Dijikstra und Minimal spanning tree verwenden könnte?

Für minimal spanning tree dachte ich mir ein wlan Anbieter der neue Kabeln anlegt und jedes Haus mit geringsten Gesamtkosten verbinden will. Wie wäre es bei Dijikstra?

...zur Frage

Dag in Deutschland?

Kennt man dag in Deutschland und Verwendet man das auch?

Hier in Österreich bestellt man Feinkost in dag.

dag = Dekagram

...zur Frage

NFA in DFA überführen Potenzmenge sehr groß?

Hallo,

ich wäre sehr dankbar, wenn mir jemand im Teil b) der Aufgabe weiterhelfen könnte:

Meine Lösung a)

0(1)*(101|01(0)*0)(0*1*)* als regulärer Ausdruck

b) Die Nichtdeterminus Stellen habe ich markiert im NFA

Jetzt soll man noch den NFA in einen DFA überführen. Normal bildet man doch jetzt die PotzenMenge, dies wären 2^7 = 128 Zustände (und arbeitet dort die Verbindungen ab...)

=> Dies kann man doch sicherlich einfacher lösen.

Bitte es so erläutern, dass es auch jemand versteht der nicht Profi in den Formalen Sprachen ist. Danke!

=> Wie sähe der DFA am Ende aus?

...zur Frage

Zeitregel beim Handball?

Wie ist die?? Wie lange darf man vor dem gegnerischen Tor spielen, ohne dass es Zeitspiel ist??

...zur Frage

Unterschied zwischen Kreis und Zyklus Graphentheorie?

Moin, Titel sagt alles. Was ist der unterschied zwischen einem Kreis und einem Zyklus in einem Graphen?

...zur Frage

Ternärer Baum als Pseudocode?

In dieser Aufgabe betrachten wir gewurzelte ternäre Bäume. Jeder Knoten v kann also ein linkes Kind v.L, ein mittleres Kind v.M und/oder ein rechtes Kind v.R haben. Wir möchten nun herausfinden, wie viele Knoten im Baum sind.Gebe jeweils einen rekursiven Algorithmus in Pseudocode an, der durch den Aufruf count(v0) die Anzahl n der Knoten im Baum mit Wurzel v0 bestimmt. Begründe die Korrektheit der Algorithmen.

a) Gehe für den Entwurf deines Algorithmus zuerst davon aus, dass der Baum vollständig ist, also jeder Knoten entweder genau drei Kinder oder gar kein Kind besitzt und für jedes Blatt der Weg von der Wurzel die gleiche Länge hat. Stelle eine Rekursionsgleichung für die Laufzeit auf und löse diese mithilfe des Master-Theorems. Der Algorithmus soll eine Laufzeit von o(n)haben.

b) Wie verändern sich Algorithmus und Laufzeit, wenn Sie allgemeine ternäre Bäume betrachten?

________________________________________________________

Es geht um Pseudo-Code. In der Vorlesung benutzen wir C (obwohl wir C eigentlich erst nächstes Semester lernen), also wir lassen immer Klammern auf und schließen diese erst in der nächsten oder ubernächsten Zeile und erhöhen Variablen durch i++.

Ich habe mir überlegt, weil das ganze ein ternärer Baum sein soll und die Länge gezählt wird:

var counter = 0
    for b = 0; b ≤ n; b++) {
        for (l = 1, l++) {
             l = l + 1
}
        for (m = m, m++) {
             m = m + 1
}
        for (r = r, r++) {
             r = r + 1
}
        counter = counter + 1
}

wobei b die, ich nenn's jetzt einfach mal "Oberschleife" ,für den Baum an sich ist und l, m und r jeweils Unterschleifen, wobei l = links, m = mitte, r = rechts. Glaube aber, dass ich's mir hiermit zu einfach mache.

Zudem muss das Ganze ja noch als rekursive Funktion geschrieben werden, also der Form T (n) = a * T (n/b) + f(n), wobei b in diesem Fall = 3 ist, weil es ja ein ternärer Baum ist. Aber was ist a? Man könnte ja theoretisch unendlich viele Kinderknoten haben? Oder versteh ich da was falsch?

...zur Frage

Regulärer Ausdruck zu NFA/NEA?

Kann mir bitte Jemand weiterhelfen, diesen NFA/NEA zu konstruieren?

Mit "alle drei" Automaten sind jeweils der Automat von [0-9], [0-9]* und [0-9][0-9]* gemeint.

Für [0-9] habe ich den Automaten:

-->(q0)----[0-9]---->((q2))

Für die restlichen beiden habe ich auch eine Lösung, jedoch wurde mir gesagt, dass wir Epsilon bzw. Lambda nicht benutzen dürfen.

Ich verstehe jedoch nicht wie ich dann 5 Zustände und 6 Kanten erreichen soll beim finalen Automat.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen