Categoría: Dijkstra

Costo mínimo de ruta entre Nodes dados que contienen como máximo K Nodes en un gráfico dirigido y ponderado

Posted on by Rudeus Greyrat

Dado un gráfico ponderado dirigido representado por un gráfico de array 2-D [][] de tamaño n y 3 enteros src, dst yk que representan el punto de origen, el punto de destino y el número disponible de paradas. La tarea es minimizar el costo del camino entre dos Nodes que contienen como máximo K Nodes … Continue reading «Costo mínimo de ruta entre Nodes dados que contienen como máximo K Nodes en un gráfico dirigido y ponderado»

Comparación de los algoritmos de Dijkstra y Floyd-Warshall

Posted on by Rudeus Greyrat

Propósitos principales: El algoritmo de Dijkstra es un ejemplo de un algoritmo SSSP o más corto de fuente única, es decir, dado un vértice fuente, encuentra la ruta más corta desde la fuente hasta todos los demás vértices. El algoritmo Floyd Warshall es un ejemplo de algoritmo de ruta más corta de todos los pares, … Continue reading «Comparación de los algoritmos de Dijkstra y Floyd-Warshall»

Casa de conejos | Google Kickstart 2021 Ronda A

Posted on by Rudeus Greyrat

Bárbara obtuvo muy buenas calificaciones en la escuela el año pasado, por lo que sus padres decidieron regalarle un conejo como mascota. Estaba tan emocionada que construyó una casa para el conejo, que se puede ver como una cuadrícula 2D con filas RR y columnas CC. A los conejos les encanta saltar, así que Bárbara … Continue reading «Casa de conejos | Google Kickstart 2021 Ronda A»

Encuentre la distancia máxima más corta en cada componente de un gráfico

Posted on by Rudeus Greyrat

Dado un gráfico de array de adyacencia [][] de un gráfico ponderado que consta de N Nodes y pesos positivos, la tarea de cada componente conectado del gráfico es encontrar el máximo entre todas las distancias más cortas posibles entre cada par de Nodes . Ejemplos: Aporte: Producción: 8 0 11  Explicación : hay tres … Continue reading «Encuentre la distancia máxima más corta en cada componente de un gráfico»

Algoritmo de ruta más corta de Dijkstra usando set en STL

Posted on by Rudeus Greyrat

Dado un gráfico y un vértice de origen en el gráfico, encuentre los caminos más cortos desde el origen hasta todos los vértices en el gráfico dado. Input : Source = 0 Output : Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 … Continue reading «Algoritmo de ruta más corta de Dijkstra usando set en STL»

Número de rutas más cortas distintas del Node 1 a N en un gráfico ponderado y dirigido

Posted on by Rudeus Greyrat

Dado un gráfico dirigido y ponderado de N Nodes y M aristas, la tarea es contar el número de caminos de menor longitud entre el Node 1 y N. Ejemplos: Entrada: N = 4, M = 5, aristas = {{1, 4, 5}, {1, 2, 4}, {2, 4, 5}, {1, 3, 2}, {3, 4, 3}} Salida: … Continue reading «Número de rutas más cortas distintas del Node 1 a N en un gráfico ponderado y dirigido»

Búsqueda de costo uniforme (Dijkstra para gráficos grandes)

Posted on by Rudeus Greyrat

Uniform-Cost Search es una variante del algoritmo de Dijikstra . Aquí, en lugar de insertar todos los vértices en una cola de prioridad, insertamos solo la fuente, luego insertamos uno por uno cuando sea necesario. En cada paso, verificamos si el elemento ya está en la cola de prioridad (usando la array visitada). En caso … Continue reading «Búsqueda de costo uniforme (Dijkstra para gráficos grandes)»

Ruta con suma mínima XOR de aristas en un gráfico dirigido

Posted on by Rudeus Greyrat

Dado un grafo dirigido con N Nodes y E aristas, un origen S y un destino D Nodes. La tarea es encontrar el camino con la mínima suma XOR de aristas de S a D. Si no hay una ruta de S a D , imprima -1 . Ejemplos:   Entrada: N = 3, E = … Continue reading «Ruta con suma mínima XOR de aristas en un gráfico dirigido»

¿Por qué falla el algoritmo de Dijkstra en pesos negativos?

Posted on by Rudeus Greyrat

Algoritmo de Dijkstra : es un algoritmo de búsqueda de gráficos que utiliza un enfoque codicioso para encontrar la ruta más corta desde el Node de origen hasta todos los demás Nodes restantes . Resuelve el problema de la ruta más corta de fuente única para un gráfico ponderado. Este algoritmo realiza un seguimiento de … Continue reading «¿Por qué falla el algoritmo de Dijkstra en pesos negativos?»

Ciclo más corto en un gráfico no ponderado no dirigido

Posted on by Rudeus Greyrat

Dado un gráfico no ponderado no dirigido. La tarea es encontrar la duración del ciclo más corto en el gráfico dado. Si no existe ningún ciclo, imprima -1. Ejemplos:   Aporte:  Salida: 4  Ciclo 6 -> 1 -> 5 -> 0 -> 6 Aporte:  Salida: 3  Ciclo 6 -> 1 -> 2 -> 6  Requisitos previos: … Continue reading «Ciclo más corto en un gráfico no ponderado no dirigido»