algorithm - redes - ¿El Árbol de expansión mínimo teme a los pesos negativos?

modelo de redes

Question

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 Shortest Path (SP) tiene problemas con los pesos negativos, ya que suma todos los pesos a lo largo de las rutas e intenta encontrar el mínimo.

Pero no creo que el Árbol de expansión mínima (MST) tenga problemas con los pesos negativos, ya que simplemente toma el límite de peso mínimo sin preocuparse por el peso total general.

¿Estoy en lo cierto?

Answer 1

Sí, tiene usted 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, puede agregar una gran constante positiva a todos los bordes de su gráfica, haciendo que todos los bordes sean positivos. El MST (como un subconjunto de bordes) seguirá siendo el mismo.

Answer 2

Sí, tienes razón porque si ves el algoritmo de la ruta más corta como dijkstera, comprobará si la distancia actual del vértice v es mayor que la suma del valor presente + el peso del borde, entonces cambiará el valor de distancia del vértice v de s por el valor de la suma y si el peso del borde es negativo, entonces dará algunos problemas.

Pero en el problema de MST hay algoritmos como prims, kruskal que toman solo el límite de peso mínimo para que el borde negativo califique para MST.