Graphen

[Gast]

Hallo,

habe eine kurze Frage. Vielleicht kennt sich ja jemand mit der Graphentheorie aus. Ich habe eine Adjazenzmatrix eines zusammenhängenden gerichteten Graphen mit bewerteten Kanten. Jetzt finde ich überall Algorithmen um die kürzesten Wege zu berechnen, ich möchte aber alle Wege berechnen. Weiß vielleicht jemand etwas über einen Algorithmus der dies bewerkstelligt ?
Habe wirklich lange gesucht und nichts dazu gefunden.

Danke

 

[Gast]

Naja, man sollte dabei vllt berücksichtigen, das es unter umständen unendlich viele Wege gibt.

Gibt es einen Weg

A B C A,

so wird es auch einen Weg
A B C A B C A
A B C A B C A B C A
A B C A B C A B C A B C A

Was hat das nun mit deinem Problem zu tun?

Ich weiß es nicht, aber man muß sich gedanken machen wie so ein Algorithmus terminieren soll. Sprich wie soll das Ding mit Cyclen umgehen.

 

[Gast]

Ja, danke erstmal,

das Problem dürfte es bei mir nicht geben. Es ist wie schon gesagt ein gerichteter Graph und ich darf, bzw. muss einen Knoten nur einmal besuchen. Also ich will z.B. von A nach Z über B,C;D, wobei es z.B. von A nach B zwei Möglichkeiten gibt, also zwei unterschiedlich lange Wege welche über keinen weiteren Knoten führen und dies ist nun bei jeder Kante der Fall. Ich will jetzt einfach alle Kombinationen auflisten. Hat niemand einen Ansatzstichpunkt ?

Vielen Dank

 

[Marco13]

Die meisten Algorithmen kann man (wenn man sie "verstanden" hat) verallgemeinern auf das finden von mehreren kürzesten Wegen. Allerdings ist deine Problembeschreibung nicht genau genug. Du sagtest, dass du "alle" Wege berechnen willst. Das willst du vermutlich nicht. (Du musst aber schon die Frage stellen, auf die du die antwort haben willst).

http://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms

Mit dem Dijkstra kann man die kürzesten Wege von einem Knoten zu allen anderen Knoten finden. Mit dem Floyd-Warshall kann man den kürzesten Weg zwischen allen Paaren von Knoten finden. Wenn es (egal, bei welchem Algorithmus) ZWEI oder merh kürzeste Wege von A nach B gibt, muss man sich was überlegen...