Se dice que una gráfica dirigida es antipática si para cualquiera de los dos vértices y v en la gráfica G = ( V , E ) , hay como máximo una ruta simple de u a v .
Supongamos que se me da un gráfico antipatía tal que cada borde tiene un peso positivo o negativo, pero no contiene ciclos de peso negativos.
A partir de esto, quiero encontrar un algoritmo que encuentre todas las rutas más cortas a todos los nodos desde un nodo fuente s .
No estoy seguro de cómo abordaría este problema. Estoy tratando de ver cómo podría usar el hecho de que no contiene ciclos de peso negativos y, por supuesto, como máximo, una ruta simple entre cualquier nodo a v .
algorithms
graphs
gprime
fuente
fuente
Respuestas:
Elige una representación de datos
Primero, mira el tamaño del resultado. Desea la colección de rutas más cortas de a todos los demás nodos. A menos que la longitud promedio de una ruta esté limitada por una constante (que no lo es: cualquier lista es unipath, y si toma la raíz para s, la longitud total de las rutas es n ( n - 1 ) / 2 donde n es la longitud de la lista), deberá ser cuidadoso en su representación de datos: la estructura que contiene las rutas deberá usar el intercambio entre rutas.s s n(n−1)/2 n
Propongo almacenar el resultado en una matriz, indexada por nodos numerados del al | E | - 1 , con s = 0 . Cada elemento de la matriz almacena el índice del nodo anterior en la ruta a ese nodo (use, por ejemplo, - 1 como marcador especial para los nodos a los que no se puede acceder desde s ). La ruta de s a t será ( s = R [ ... R [ t ] ... ] , ... , R [ R [ t0 |E|−1 s=0 −1 s s t .(s=R[…R[t]…],…,R[R[t]],R[t],t)
Recorrer el gráfico
Inicializar a todos - 1 .R −1
Realice un recorrido de la gráfica primero en profundidad o en anchura a partir de . Cada vez que se alcanza un nodo u , establezca R [ u ] en su predecesor.s u R[u]
Como hay ciclos, se puede llegar a un nodo más de una vez. Tener indica que T ya ha sido visitado.R[u]≠−1 u
Probar la corrección
Probar la complejidad
Bien entonces. Probemos que en un gráfico unipático, el número de ciclos elementales crece como máximo linealmente con el número de nodos. (Un ciclo elemental es uno que no contiene un ciclo más corto). En la siguiente discusión, supondré que el gráfico no tiene borde propio (ningún borde de un nodo en sí mismo; tales bordes son irrelevantes para la construcción de la ruta de todos modos )
Los gráficos unipáticos pueden tener ciclos, pero de una manera muy limitada. Sería bueno si de alguna manera pudiéramos asociar cada ciclo a un nodo distinto (o al menos, como máximo, un número limitado de ciclos por nodo). ¿Pueden los ciclos compartir un nodo? Por desgracia sí.
fuente