L'albero di copertura minimo ha paura dei pesi negativi?

Questa è una domanda di follow-up di Why most graph algorithms do not adapt so easily to negative numbers?.L'albero di copertura minimo ha paura dei pesi negativi?

penso Shortest Path (SP) ha problema con i pesi negativi, perché aggiunge il backup di tutti i pesi lungo i sentieri e cerca di trovare quello minimo.

Ma non penso che lo strumento di spaziatura minimo (MST) abbia problemi con i pesi negativi, perché prende solo il bordo del peso minimo singolo senza preoccuparsi del peso totale complessivo.

Ho ragione?

fonte

2012-05-02 Jackson Tale

considerato [informatica @ StackExchange] (http://cs.stackexchange.com/)? – HongboZhu

@HongboZhu sì, forse la prossima volta –

BTW quando tutti i bordi nel grafico sono negativi, trovare il percorso più breve è lo stesso problema di trovare il percorso più lungo per il grafico con i bordi etichettati con il valore assoluto della loro lunghezza originale. Il problema del percorso più lungo è noto per essere NP-difficile. – Palec

Sì, hai ragione. Il concetto di MST consente pesi di un segno arbitrario. I due algoritmi più popolari per trovare MST (Kruskal's e Prim's) funzionano bene con bordi negativi.

In realtà, si può semplicemente aggiungere una grande costante positiva a tutti i bordi del grafico, rendendo tutti i bordi positivo. L'MST (come sottoinsieme di spigoli) rimarrà lo stesso.

fonte

2012-05-02 12:54:21 Skiminok

Il fatto che un albero che è un sotto-grafico di un grafico abbia un numero fisso di spigoli a seconda del numero di vertici, quindi l'aggiunta di un numero 'p' a ogni spigolo aumenta il costo generale di' pE'. Non è vero trovare il percorso più breve, perché i percorsi più brevi possono essere costituiti da un numero diverso di spigoli. – enedil

I due algoritmi più popolari per la ricerca di MST (Kruskal's e Prim's) funzionano bene con bordi negativi perché lavorano su grafici non orientati – raghavsood33

Sì, hai ragione perché se vedi l'algoritmo per il percorso più breve come dijkstera controllerà se la distanza attuale del vertice v è maggiore della somma del valore attuale + peso del bordo allora cambierà il valore della distanza del vertice v da s per il valore di somma e se il peso del bordo è negativo allora darà alcuni problemi.

Ma il problema MST esistono algoritmi come prim, Kruskal che prendono soltanto il bordo minimo peso in modo che fanno fronte negativo beneficiare di MST.

fonte

2017-02-13 08:05:19

L'albero di copertura minimo ha paura dei pesi negativi?

risposta

Problemi correlati