Längsmöglicher kürzester Weg zwischen Knoten im Graph

[scooter010]

Moin!

Als kleines Hobbyprojekt versuche ich in einem Grapen aus n Knoten mit m Kanten (Verbindungen nicht biderektional sondern als Einbahnstraße, also hat eine bidirektionale Verbindung zwischen 2 Knoten 2 Kanten) den betragsmäßig größten Wert für alle kürzeste Verbindungen zwischen je 2 Knoten von allen Knoten im Graphen zu ermitteln. Der Länge der Kanten ist immer 1.

Anders ausgedrückt: Ich möchte wissen, welche Knoten im Graphen bei Verwendung des jeweils kürzesten Weges zwischen diesen am weitesten voneinander entfernt liegen. Ich gehe davon aus, dass ich für alle Knotenkombinationen den jeweils kürzesten Weg bestimmen muss um anschließend zu prüfen, wwelcher der "längste kürzeste" Weg ist. Ein "längster" Weg Algorythmus hilft nicht, da dieser "absichtlich" Umwege nehmen wird.
Gibt es sowas schon?

Letztendlich geht es darum, das Spiel "komme von Wiki-Artikel A nur durch Nutzung Artikel-interner Links (ohne Menüleiste, sondern nur Links im Artikelinhalt) zu Wiki-Artikel B" möglichst effizient zu kösen bzw. Schwierigkeitsgrade für Artikelpaare zu ermitteln. Aber zuerst: Welche Artikel sind am Weitesten "voneinander entfernt".

Jemand Ideen?

 

[hallo7]

Du suchst also den längsten Weg zwischen zwei Knoten, aber jeder Knoten darf nur einmal besucht werden? Oder anders formuliert, du suchst den Weg zwischen zwei Knoten bei dem möglichst viele andere Knoten genau einmal besucht werden?

 

[scooter010]

Nein. Ich möchte wissen, zwischen welchen beiden Knoten (vielleicht gibt es mehrere Knotenpaare) der kürzeste Weg länger als zwischen allen anderen Knoten ist.

 

[hallo7]

Ah ok. Also das Knotenpaar mit dem längsten kürzesten Weg herausfinden.

Ja, da heißt es wohl den kürzesten Weg für alle Paare berechnen und dann den längsten nehmen. Je nach Knoten Anzahl geht das ja recht schnell - skaliert halt nicht gut Seh aber auch keine bessere Möglichkeit.

 

[scooter010]

Je nach Knoten Anzahl geht das ja recht schnell

Für alle Wikipedia-Einträge ...

 

[hallo7]

Also ca. 56 Mio, das sollte schon gehen, die werden ja nicht sonderlich dicht verknüpft sein.

 

[scooter010]

Eine Stichprobe von rd. 6000 Artikeln ergab rund 22.000 Kanten und alleine dafür waren 40 GB Ram nicht genug...

 

[hallo7]

Wofür brauchst du soviel RAM wenn die Kanten alle mit 1 gewichtet sind? Normalerweiße fressen die unterschiedlichen Kantengewichte RAM, aber die musst du in dem Fall nicht speichern.
Was verwendest du zum berechnen?

Ich hab vor einigen Jahren einen Graphen mit 20 000 nodes und 100 000 Kanten kürzeste Wege und noch viele weitere Parameter auf meinen Laptop berechnet, der hatte 8GB RAM (hat ca. 20 Stunden gedauert damals)

Ansonsten schonmal den Graphen untersucht, ob wirklich alles verbunden ist oder mehrere Cluster vorhanden sind?