Si el gráfico es escaso, es probable que desee algún tipo de representación de lista de borde como su estructura de datos principal en lugar de una solución de matriz basada en matriz, que es cómo funciona Floyd-Warshall.
Este problema ha sido atacado anteriormente de varias maneras (http://www.w3.org/TR/rdf-sparql-…), pero creo que sería un gran proyecto de investigación simple. Mis sugerencias:
- Primero descubra la semántica y la sintaxis de su lenguaje de consulta y manténgalo básico. Analizar un lenguaje de consulta puede no ser trivial en sí mismo, y probablemente no quiera pasar la mayor parte de su tiempo en él.
- Recuerda el wazoo. Una implementación clásica de Dijkstra implica hacer de cada nodo un montón, con los miembros del montón como los bordes y sus pesos en el gráfico original. En esencia, comienza con el montón del nodo en el que comienza, hace estallar su raíz, luego se une con el montón de la raíz anterior, vuelve a apilar y luego continúa hasta llegar al destino. Esto encuentra su camino más corto (o más largo) muy rápidamente – O (| E | log | V |), de hecho.
- Almacene los resultados de los cálculos intermedios lo mejor que pueda en un tipo de caché o DP. Las soluciones recursivas ingenuas en un gráfico disperso no trivial serán enormemente costosas en términos de tiempo, por lo que cualquier cosa que pueda hacer para optimizarlo será útil.
- Puede valer la pena mantener una representación basada en matriz para ciertas operaciones que desea hacer. Por ejemplo, puede encontrar fácilmente todas las rutas de longitud N desde cualquier fila R a cualquier columna C exponiendo la matriz N veces.
- ¿Cuántos rectángulos de 3 × 5 caben en un rectángulo de 18 x 26? ¿Hay una manera simple de calcular?
- Cómo hacer que el siguiente código sea mejor y más eficiente para el problema de invertir las palabras en la oración dada
- ¿Cuál es el vínculo entre los algoritmos de optimización y las distribuciones de probabilidad?
- ¿Qué representación gráfica es mejor para la programación competitiva en C ++: lista de adyacencia o matriz de adyacencia?
- ¿Por qué estudiamos diferentes algoritmos para la misma tarea?
