Algorithmen

Question 1

Dijkstra

Answer 1

Tabelle mit allen Knoten
der Knoten mit dem kürzesten Weg ist immer der Arbeitsknoten, ausgehend vom Startknoten

gibt den kürzesten Weg vom Startknoten zu einem beliebigen Knoten an

Question 2

Kruskal

Answer 2

1. kürzeste Kante markieren
2. nächstkürzeste Kante markieren
   - Kreis? Kante doch nicht markieren!
   Ende: alle Knoten sind zusammenhängend

Question 3

Adjazenzmatrix

Answer 3

1=Verbindung von Knoten i nach j ist vorhanden
0=…ist nicht vorhanden

nxn-Matrix mit n Knoten

Question 4

Inzidenzmatrix

Answer 4

-1=Knoten ist Endpunkt einer Kante
0=0
1=Knoten ist Startpunkt einer Kante

nxm Matrix mit n Knoten und m Kanten

Question 5

Bellmann-Ford

Answer 5

Bewertungsmatrix:

• Kante ist vorhanden: Eintrag ist das Gewicht
• i=j: der Eintrag ist 0
• Kante existiert nicht: Eintrag ist unendlich

Treematrix: T^(k)(g)

• Kante ist vorhanden: Eintrag ist der Vorgängerknoten
• Kante ist nicht vorhanden: Eintrag ist -1

“Arbeitsmatrix (?)”: U^(k)(g)

• U^(1) ist die Bewertungsmatrix
• U^(k)=U^(k-1) Bellmann-multipiziert U^(1)
• T^(k) gibt als Pärchenmatrix dazu den Vorgängerknoten an

Question 6

Bellmannmultiplikation

Answer 6

X(x)Y=C mit cij=min{xik + ykj}

oder: min{jeweiliger Spalteneintrag von U^(1) + jeweiliger Zeileneintrag von U^(k)

Question 7

Abbruchkriterien Bellmann-Ford

Answer 7

• neg. Einträge auf Hauptdiagonalen (wahrscheinlich negativer Zyklus)
• Einträge der U-Matrix bleiben in der nächsten Iteration gleich? Optimum gefunden!
• maximal |V|-1 Durchläufe! Danach noch einen um auf neg. Zyklus zu testen; V ist Anzahl der Punkte eines Graphen