Categoría: Shortest Path

Ruta de costo mínimo con movimientos permitidos hacia la izquierda, derecha, abajo y arriba

Posted on by Rudeus Greyrat

Dada una cuadrícula bidimensional, cada celda de la cual contiene un costo entero que representa un costo para atravesar esa celda, necesitamos encontrar un camino desde la celda superior izquierda hasta la celda inferior derecha por el cual el costo total incurrido sea mínimo. Nota: Se supone que los ciclos de costos negativos no existen … Continue reading «Ruta de costo mínimo con movimientos permitidos hacia la izquierda, derecha, abajo y arriba»

Número de rutas más cortas para llegar a cada celda desde la celda inferior izquierda de la cuadrícula

Posted on by Rudeus Greyrat

Dados dos números N y M . La tarea es encontrar el número de caminos más cortos para llegar a la celda (i, j) en la cuadrícula de tamaño N × M cuando los movimientos comenzaron desde la esquina inferior izquierda . Nota: la celda (i, j) representa la i-ésima fila y j-ésima columna en … Continue reading «Número de rutas más cortas para llegar a cada celda desde la celda inferior izquierda de la cuadrícula»

La ruta más corta en Matrix desde la esquina superior izquierda hasta la esquina inferior derecha con vecinos que superan como máximo K

Posted on by Rudeus Greyrat

Dada una array mat[][] y un entero K, la tarea es encontrar la longitud del camino más corto en una array desde la esquina superior izquierda hasta la esquina inferior derecha tal que la diferencia entre los Nodes vecinos no exceda K. Ejemplo: Entrada: mat = {{-1, 0, 4, 3}, K = 4, src = … Continue reading «La ruta más corta en Matrix desde la esquina superior izquierda hasta la esquina inferior derecha con vecinos que superan como máximo K»

Ruta más larga en un gráfico acíclico dirigido

Posted on by Rudeus Greyrat

  Dado un gráfico cíclico dirigido ponderado ( DAG ) y un vértice fuente en él, encuentre las distancias más largas desde s hasta todos los demás vértices en el gráfico dado. El problema de la ruta más larga para un gráfico general no es tan fácil como el problema de la ruta más corta … Continue reading «Ruta más larga en un gráfico acíclico dirigido»

Diferencia entre el árbol de expansión mínimo y la ruta más corta

Posted on by Rudeus Greyrat

Árbol de expansión : Un árbol de expansión (T) de un grafo no dirigido (G) es un subgrafo que es un árbol que incluye todos los vértices de un grafo (G) y el número mínimo de aristas necesarias para conectar el grafo (G) . Y es un conjunto máximo conocido de aristas sin ciclos. Propiedades: … Continue reading «Diferencia entre el árbol de expansión mínimo y la ruta más corta»

Problema de la serpiente y la escalera

Posted on by Rudeus Greyrat

Dado un tablero de serpientes y escaleras, encuentre el número mínimo de lanzamientos de dados necesarios para llegar al destino o la última celda desde el origen o la primera celda. Básicamente, el jugador tiene control total sobre el resultado del lanzamiento de dados y quiere averiguar el número mínimo de lanzamientos necesarios para llegar … Continue reading «Problema de la serpiente y la escalera»

Ruta de costo mínimo en una array moviéndose solo en la diferencia de valor de X

Posted on by Rudeus Greyrat

Dada una array mat[][] y un entero X , la tarea es encontrar el número mínimo de operaciones requeridas para llegar   desde  . En cada movimiento, podemos movernos hacia la derecha o hacia abajo en la array, pero para movernos a la siguiente celda de la array, el valor de la celda debe ser  . … Continue reading «Ruta de costo mínimo en una array moviéndose solo en la diferencia de valor de X»

Ruta más corta en gráfico acíclico dirigido

Posted on by Rudeus Greyrat

Dado un gráfico acíclico dirigido ponderado y un vértice fuente en el gráfico, encuentre las rutas más cortas desde la fuente dada a todos los demás vértices. Para un gráfico ponderado general, podemos calcular las distancias más cortas de una sola fuente en tiempo O (VE) utilizando el algoritmo Bellman-Ford . Para un gráfico sin … Continue reading «Ruta más corta en gráfico acíclico dirigido»

Ruta de costo mínimo en un gráfico dirigido a través de un conjunto dado de Nodes intermedios

Posted on by Rudeus Greyrat

Dado un gráfico dirigido y ponderado G , una array V[] que consta de vértices, la tarea es encontrar la ruta de costo mínimo que pasa por todos los vértices del conjunto V , desde una fuente S dada hasta un destino D . Ejemplos:  Entrada: V = {7}, S = 0, D = 6   … Continue reading «Ruta de costo mínimo en un gráfico dirigido a través de un conjunto dado de Nodes intermedios»

Encuentra la distancia más corta desde un guardia en un banco

Posted on by Rudeus Greyrat

Dada una array que está llena de ‘O’, ‘G’ y ‘W’ donde ‘O’ representa un espacio abierto, ‘G’ representa guardias y ‘W’ representa paredes en un banco. Reemplace todas las O en la array con su distancia más corta de un guardia, sin poder atravesar ninguna pared. Además, reemplace los protectores con 0 y las … Continue reading «Encuentra la distancia más corta desde un guardia en un banco»