Algorithmusentwurf für Bandbreite Verfügbarkeit

Question

Ich habe ein Diagramm von N Knoten. Ich habe den Bandbreitenverbrauch aller Links. Eine Verbindung mit der geringsten Bandbreite, die in einem Pfad von Knoten s zu Knoten t verfügbar ist, wird als Flaschenhals des Pfads bezeichnet. Um die Bandbreitenverfügbarkeit zwischen Knoten s und Knoten t zu finden, führe ich ein DFS aus, um N Anzahl von Pfaden zwischen den zwei Knoten zu finden, und dann finde ich einen Engpass für jeden Pfad. Ich nehme dann im Durchschnitt diese Engpässe, um einen durchschnittlichen Engpass zu finden. Kann ich dies als eine einzige Nummer verwenden, um die Verfügbarkeit der Bandbreite zwischen Knoten s und Knoten t zu bezeichnen? Was sind die Vor- und Nachteile? Bitte schlagen Sie mir einen geeigneten Ort vor, um zu fragen, ob dies nicht der richtige Ort ist.

Answer 1

Es klingt wie das, was Sie suchen ist Netzwerk-Flow Analysis, insbesondere Max flow, Min Cut.

Ihre aktuelle Implementierung ignoriert die Tatsache, dass Sie Daten entlang mehreren Pfaden zu senden, sobald möglicherweise in der Lage.

Eine letzte Anmerkung - Sie können den Algorithmus von Djikstra verwenden, um den Pfad mit dem größten Engpass zu finden.