¿Minimum Spanning Tree teme los pesos negativos?
Esta es una pregunta de seguimiento de ¿Por qué la mayoría de los algoritmos de gráficos no se adaptan tan fácilmente a los números negativos?.
Creo que el Camino más corto (SP) tiene problemas con los pesos negativos, porque suma todos los pesos a lo largo de los caminos e intenta encontrar el mínimo.
Pero no creo que Minimum Spanning Tree (MST) tenga problemas con los pesos negativos, porque solo toma el borde de peso mínimo sin preocuparse por los pesos totales generales.
Soy ¿verdad?
2 answers
Sí, tienes razón. El concepto de MST permite pesos de un signo arbitrario. Los dos algoritmos más populares para encontrar MST (Kruskal y Prim) funcionan bien con bordes negativos.
En realidad, solo puedes agregar una gran constante positiva a todos los bordes de tu gráfico, haciendo que todos los bordes sean positivos. El MST (como un subconjunto de aristas) seguirá siendo el mismo.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-05-02 12:54:21
Sí, tiene razón porque si ve el algoritmo para el camino más corto como dijkstera comprobará si la distancia actual del vértice v es mayor que la suma del valor actual + peso del borde, entonces cambiará el valor de la distancia del vértice v de s por el valor de suma y si el peso del borde es negativo, entonces dará algunos problemas.
Pero en el problema MST hay algoritmos como prims, kruskal que toman solo el borde de peso mínimo para que el borde negativo califique para MST.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-02-13 08:05:19