Cos'è un percorso minimo in un grafico?

Question

Nella teoria dei grafi, qual è la distinzione tra distanza minima (che trova l'algoritmo di Dijkstra) e percorso minimo (che non sono sicuro di cosa si tratti)?

Answer 1

Il percorso minimo è l'insieme dei bordi che, quando attraversati, coprono la minima distanza tra due bordi. La distanza minima è la somma della distanza tra i bordi di un percorso minimo.

Answer 2

la distanza è scalare; un numero. path è un elenco di coppie vertice / bordo?

Answer 3

Distanza minima = somma minima dei pesi del bordo. Percorso minimo = minimi bordi.

Ie // È un percorso più breve per volare da Vancouver a Toronto e poi a Winipeg anche se è una distanza più breve per volare da Vancouver a Calgary a Regina e poi a Winipeg.

Modifica: capovolgilo, penso.

Answer 4

Non sono sicuro al 100%, ma sembra che il percorso minimo sia l'elenco dei vertici visitati quando si percorre il percorso di distanza minima dal vertice A al vertice B.

Answer 5

Lasciami rispondere a questa domanda nell'ambito di una rete con una sorgente e un sink. Vorrei distinguere tra un percorso più breve e un percorso minimo, in cui un percorso è definito da una serie di spigoli.

Un percorso più breve è un percorso dalla sorgente al sink che ha la distanza corrispondente più breve. Un percorso minimo può essere qualsiasi percorso che collega l'origine al sink fintanto che

i) non contiene cicli; e

ii) la rimozione di uno qualsiasi dei bordi dal percorso significa che non esiste più una connessione tra sorgente e sink.

Answer 6

La distanza minima è la stessa del percorso minimo.