Graphenalgorithmen

Wissenschaft Informatik
#1

Erstmal ein Hallo an alle,

ich bin auf der Suche nach Algorithmen für Graphen. Dabei gilt folgendes:

  1. gerichtete Graphen
  2. unbewertete Graphen (alle Kanten können aber mit 1 bewertet werden)

Ich such nun:
a) einen Algorithmus für die Wege, welche wenige Kanten und Knoten berühren (kürzeste)
b) einen Algorithmus für die längsten Wege.

Dabei sollen diese Algorithmen
I) implementiert werden
II) auch auf einem Zettel nachvollzogen
werden können.
Wäre Spitze, wenn mir jemand helfen kann.

Gruss
muecke99

#2

Erstmal ein Hallo an alle,

ich bin auf der Suche nach Algorithmen für Graphen. Dabei gilt
folgendes:

  1. gerichtete Graphen
  2. unbewertete Graphen (alle Kanten können aber mit 1 bewertet
    werden)

Ich such nun:
a) einen Algorithmus für die Wege, welche wenige Kanten und
Knoten berühren (kürzeste)

Dijkstra. (Überall im Netz)

b) einen Algorithmus für die längsten Wege.

Ist in ungerichteten und in nicht azyklischen Fällen NP-Hart sprich kein schöner Algorithmus in Sicht.

Im Azyklsichen Fall-> Erst Topologisch sortieren, dann in dieser Reihenfolge jeweils das maximum über alle Vorgänger nehmen (wird z.B. im OR bei der sog. CPM-Methode benutzt).

MfG
ML
Agorithmus in Sicht.

Dabei sollen diese Algorithmen
I) implementiert werden
II) auch auf einem Zettel nachvollzogen
werden können.
Wäre Spitze, wenn mir jemand helfen kann.

Gruss
muecke99

#3

Erstmal ein Hallo an alle,

ich bin auf der Suche nach Algorithmen für Graphen. Dabei gilt
folgendes:

  1. gerichtete Graphen
  2. unbewertete Graphen (alle Kanten können aber mit 1 bewertet
    werden)

Ich such nun:
a) einen Algorithmus für die Wege, welche wenige Kanten und
Knoten berühren (kürzeste)

Dijkstra. (Überall im Netz)

Schon gesucht,… Zu kürzeste gibt es wirklich ausreichend. Dijkstra hatte ich auch schon im Auge

b) einen Algorithmus für die längsten Wege.

Ist in ungerichteten und in nicht azyklischen Fällen NP-Hart
sprich kein schöner Algorithmus in Sicht.

Mir reicht eigentlich eine Heuristik. Muss auch kein „schöner“ Algorithmus sein.

Im Azyklsichen Fall-> Erst Topologisch sortieren, dann in
dieser Reihenfolge jeweils das maximum über alle Vorgänger
nehmen (wird z.B. im OR bei der sog. CPM-Methode benutzt).

Schau ich mir mal an, danke

MfG
ML
Agorithmus in Sicht.

Dabei sollen diese Algorithmen
I) implementiert werden
II) auch auf einem Zettel nachvollzogen
werden können.
Wäre Spitze, wenn mir jemand helfen kann.

Gruss
muecke99