Modificación del algoritmo de Dijkstra para pesos de borde extraídos del rango

Supongamos que tengo un gráfico dirigido con pesos de borde extraídos del rango $[1,\dots, K]$ donde $K$ es constante. Si estoy tratando de encontrar la ruta más corta utilizando el algoritmo de Dijkstra , ¿cómo puedo modificar la estructura del algoritmo / datos y mejorar la complejidad del tiempo a $O(|V|+|E|)$ ?

algorithms data-structures shortest-path weighted-graphs usuario1675999
fuente

Debe ser más específico, ¿Cuál es su estructura de datos? Y no puede obtener menos

O (V + E)

$O(V+E)$ . Revisar conferencias.

jonaprieto

El hecho de que las posibilidades de distintos pesos de borde sean pequeñas no significa que el número de distancias sea pequeño.

Joe

Primero coloree los vértices de su gráfico con azul, luego subdivida cada borde de tamaño

bordes (agregando

vértices sin color), luego ejecute el BFS en este nuevo gráfico, para encontrar las rutas más cortas desde el nodo de inicio hasta los nodos azules, es

si tiene

constante .

t

$t$

t

$t$

t - 1

$t-1$

O (| V | + | E |)

$O(|V|+|E|)$

k

$k$

@SaeedAmiri ¿por qué no escribir esto como respuesta?

Joe

@Joe porque no está modificando dijkstra (al menos directamente no está relacionado con dijkstra).

Respuestas:

Si los pesos de borde son enteros en , puede implementar Dijkstra's para que se ejecute en tiempo , siguiendo la sugerencia de @ rrenaud. Aquí hay una explicación más explícita. $\{0,1,\ldots,K\}$ $O(K|V|+|E|)$

En cualquier momento, las teclas (finitas) en la cola de prioridad están en algún rango , donde es el valor de la última clave eliminada de la cola de prioridad. (Cada clave es al menos , porque la secuencia de claves eliminadas por el algoritmo de Dijkstra no es decreciente, y cada clave es como máximo , porque cada clave tiene un valor para un poco de borde $\{D,D+1,\ldots,D+K\}$ $D$ $D$ $D+K$ $d[u] + wt(u,w)$ donde es la distancia desde la fuente a algún vértice que ya se ha eliminado, entonces ) $(u,w)$ $d[u]$ $u$ $d[u]\le D$

Debido a esto, puede implementar la cola de prioridad con una matriz circular de tamaño , con cada celda que contiene un depósito. Almacene cada vértice con la clave en el depósito en la celda donde . Realizar un seguimiento de . Realice las operaciones de la siguiente manera: $A[0..K]$ $K+1$ $k$ $A[h(k)]$ $h(k)=k \bmod (K+1)$ $D$

delete-min : Mientras está vacía, el incremento . Luego borre y devuelva un vértice de . $A[h(D)]$ $D$ $A[h(D)]$
inserte con la tecla : Agregue el vértice al cubo de . $k$ $A[h(k)]$
tecla de disminución a : mueve el vértice de a . $k$ $k'$ $A[h(k)]$ $A[h(k')]$

Insertar y disminuir clave son operaciones de tiempo constante, por lo que el tiempo total dedicado a esas operaciones será . El tiempo total de permanencia en delete-min será más el valor final de . El valor final de es la distancia máxima (finita) desde la fuente a cualquier vértice (porque un delete-min que toma iteraciones aumenta en ). La distancia máxima es como máximo $O(|V|+|E|)$ $O(|V|)$ $D$ $D$ $i$ $D$ $i$ porque cada ruta tiene como máximo aristas. Por lo tanto, el tiempo total empleado por el algoritmo es . $K(|V|-1)$ $|V|-1$ $O(K|V|+|E|)$

Neal Young
fuente

Me gusta la cola circular, eso es mucho mejor que mi idea de tener básicamente una matriz de tamaño K * v donde solo se usa una porción de tamaño av en un momento dado.

rrenaud

Lo implementé usando una lista de doble enlace, ¿eso todavía significa que es O (1) para encontrar la tecla min?

user1675999

@ user1675999, no estoy seguro. si su lista está ordenada por clave, ¿cómo inserta y disminuye la clave de manera eficiente? si su lista no está ordenada por clave, ¿cómo hacer delete-min de manera eficiente?

Neal Young el

Asumo aquí que es un número entero y los pesos de borde son integrales. De lo contrario, realmente no le compra nada, siempre puede volver a escalar los pesos para que el borde mínimo haya costado y el máximo haya costado , por lo que el problema es idéntico al problema estándar de la ruta más corta. $K$ $1$ $K$

Algoritmo / bosquejo de prueba: Implemente la cola de prioridad en este tipo de locura como una matriz de listas codificadas por costo y de otro modo usar el algoritmo estándar de Dijkstra. Mantenga un contador que rastree el costo del artículo mínimo en el montón. Resuelva la llamada en cola después de que los elementos se eliminen mediante escaneo lineal . Sí, este tipo de sonido parece una locura, pero constante $K\times |V|$ $K$ le permite engañar y engañar a su intuición algorítmica contra escaneos lineales. Solo necesita escanear desde el último marcador min porque el algoritmo de Disjkstra es bueno para su implementación de cola. En el momento en que solicita una cola, los elementos insertados en la cola son siempre mayores o iguales al mínimo anterior. El camino más largo más corto posible tiene longitud , entonces su costo de escaneo amortizado es si K es constante. $K\times |V|$ $K\times |V| = O(|V|)$

rrenaud
fuente

-2

puede usar la clasificación topológica para encontrar la solución, dejar que la fuente tenga un grado 0 y luego ir desde cada borde de la fuente, si otro vértice tiene 0 grados, luego ponerlo en la cola y seguir haciendo eso. en este caso (sin ciclo dentro del gráfico) puede alcanzar V + E ya que atravesaría cada vértice y bordes una y solo una vez.

TIANYANG ZHANG
fuente

Parece no relacionado con la pregunta? La pregunta no asume que el gráfico es acíclico, y su solución no hace uso del hecho de que los pesos se extraen de un rango constante.

xskxzr