Was ist ein minimaler Pfad in einem Diagramm?

Question

In der Graphentheorie, was ist der Unterschied zwischen minimalem Abstand (die Dijkstra-Algorithmus findet) und minimalen Pfad (was ich bin nicht sicher, was es ist)?

Answer 1

Minimal-Pfad ist der Satz von Kanten, die, wenn die Abdeckung der geringste Abstand zwischen zwei Kanten überquert. Minimalabstand ist die Summe aus dem Abstand zwischen den Kanten eines minimalen Pfades.

Answer 2

Abstand ist Skalar; eine Zahl. Pfad ist eine Liste von Scheitelpunkt / Kantenpaaren?

Answer 3

Minimal-Abstand = dest Summe Kantengewichte. Minimal path = mindestens Kanten.

Ie // Es ist ein kürzerer Weg von Vancouver nach Toronto zu fliegen und dann zu Winipeg obwohl es sich um eine kürzere Strecke ist von Vancouver nach Calgary nach Regina zu fliegen und dann zu Winipeg.

Edit: Flip, die sich um, denke ich.

Answer 4

Ich bin nicht 100% sicher, aber es klingt wie der minimale Weg die Liste von Scheitelpunkten würde besucht, wenn der minimale Distanz Pfad von Knoten A zu Vertex B durchquert.

Answer 5

Lassen Sie mich diese Frage beantworten im Rahmen eines Netzwerks mit einer Quelle und einer Senke. Ich mag zwischen einem kürzesten Weg und einem minimalen Pfad unterscheiden, in dem ein Weg durch eine Menge von Kanten definiert ist.

A kürzester Pfad ist ein Pfad von der Quelle zur Senke, dass der kürzesten entsprechenden Abstand hat. Ein minimaler Pfad kann jeder Pfad, der die Quelle zur Senke solange

verbindet

i) es keine Zyklen enthält; und

ii) Entfernung von irgendwelchen der Kanten von dem Pfad bedeutet, dass es nicht länger eine Verbindung zwischen Quelle und Senke.

Answer 6

Minimalabstand ist die gleiche wie minimaler Pfad.