Java package für die Suche in Graphen

[rosmi]

hallo,

kennt jemand eine package (die von irgendjemand programmiert wurde), wie folgendes tut:

Eingabe - ein Graph wird eingegeben (z.B. in Form einer NxN Matrix)
Einstellungen: Start- und Endpunkt festlegen
Ausgabe: Der Weg zwischen Start- und Endpunkten (z.B. als Array, oder falls mehrere Wege möglich sind - Collection von solchen Arrays )

Gruß
rosmi

 

[ADA&QS]

Es waer sinnvoll wenn du noch den gesuchten Algo. angiebst. Ich gehe davon aus das das gewicht der Kanten nur positive ist ansonsten bist im NP Bereich travelling Salesman Problem

 

[rosmi]

Graph ist gerichtet, Kantengewicht ist immer positiv (und vielleicht auch immer 1). Algorythmus spielt da keine wesentliche Rolle. Es muss lediglich der (kürzeste) Weg gefunden werden.

Ich habe mich bereits umgeschaut, und da gibt es solche Lösungen wie JUNG - ich brauche aber wirklich nur die grundlegende Funktionalität. Habe auch überlegt, selbst die benötigten Klassen zu programmieren - aber das muss wirklich nicht sein.

 

[ADA&QS]

Die Frage nach dem Algo haben ich deswegen gestellt um dir eine Hilfestellung bei der Suche zu geben Floyd und Dijkstra sind hier Algo die du verwendesten solltest

 

[rosmi]

Wie gesagt, Algorythmus spielt hier keine Rolle, weil ich das ganze nicht selbst programmieren muss (oder will), und weil ich keine bestimmte Kriterien für die Suchmethode habe.

Aber wenn wir schon bei dem Thema sind - Dijkstra hab ich schon gehört, Floyd noch nicht. Welches Algorythmus ist wohl schneller? einfacher zu implementieren? für welche Graphen besser geeignet?