Pregunta 1: Dada una gráfica ponderada dirigida. También se le proporciona la ruta más corta desde un vértice de origen ‘s’ hasta un vértice de destino ‘t’. Si el peso de cada borde aumenta en 10 unidades, ¿el camino más corto sigue siendo el mismo en el gráfico modificado? El camino más corto puede cambiar. … Continue reading «Algunas preguntas interesantes sobre el camino más corto | Serie 1»
import java.util.Scanner; //Scanner Function to take in the Input Values public class Dijkstra { static Scanner scan; // scan is a Scanner Object public static void main(String[] args) { int[] preD = new int[5]; int min = 999, nextNode = 0; // min holds the minimum value, nextNode holds the value for the … Continue reading «Programa Java para el algoritmo de Dijkstra con impresión de ruta»
Dada una array de orden N*M. Encuentre la distancia más corta desde una celda de origen hasta una celda de destino, atravesando solo celdas limitadas. También puedes moverte solo hacia arriba, abajo, izquierda y derecha. Si se encuentra, emite la distancia más -1. s representa ‘fuente’ d representa ‘destino’ * representa celda por la que puede … Continue reading «Programa Java para la distancia más corta entre dos celdas en una array o cuadrícula»
El algoritmo de Floyd Warshall es para resolver el problema de la ruta más corta de todos los pares. El problema es encontrar las distancias más cortas entre cada par de vértices en un gráfico dirigido ponderado de borde dado. Ejemplo: Input: graph[][] = { {0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, … Continue reading «Algoritmo de Floyd Warshall | DP-16 – Part 1»
El algoritmo de Johnson encuentra los caminos más cortos entre todos los pares de vértices en un gráfico dirigido ponderado . Permite que algunos de los pesos de borde sean números negativos, pero no pueden existir ciclos de peso negativo. Utiliza el algoritmo Bellman-Ford para volver a ponderar el gráfico original, eliminando todos los pesos … Continue reading «Implementación del algoritmo de Johnson para caminos más cortos de todos los pares»
Dada una array NXN (M) rellena con 1 , 0 , 2 , 3 . Encuentre el número mínimo de movimientos necesarios para pasar del origen al destino (sumidero) . mientras atraviesa celdas en blanco solamente. Puede desplazarse hacia arriba, abajo, derecha e izquierda. Un valor de la celda 1 significa Fuente. Un valor de la celda … Continue reading «Encuentre el número mínimo de movimientos necesarios para pasar de una celda de la array a otra»
Dadas las coordenadas de 3 celdas (X1, Y1) , (X2, Y2) y (X3, Y3) de una array. La tarea es encontrar la ruta mínima que conecta estas tres celdas e imprimir el recuento de todas las celdas que están conectadas a través de esta ruta. Nota: Los únicos movimientos posibles son arriba, abajo, izquierda y derecha. … Continue reading «Números mínimos de celdas que están conectadas con el camino más pequeño entre 3 celdas dadas»
Dada una array de orden N*M. Encuentre la distancia más corta desde una celda de origen hasta una celda de destino, atravesando solo celdas limitadas. También puedes moverte solo hacia arriba, abajo, izquierda y derecha. Si se encuentra, emite la distancia más -1. s representa ‘fuente’ d representa ‘destino’ * representa celda por la que puede … Continue reading «Programa C++ para la distancia más corta entre dos celdas en una array o cuadrícula»
Dado un gráfico y un vértice de origen src en el gráfico, encuentre las rutas más cortas desde src a todos los vértices en el gráfico dado. El gráfico puede contener bordes de peso negativos. Hemos discutido el algoritmo de Dijkstra para este problema. El algoritmo de Dijkstra es un algoritmo Greedy y la complejidad … Continue reading «Algoritmo de Bellman-Ford | DP-23 – Part 1»
Dado un gráfico no dirigido ponderado G y un entero S , la tarea es imprimir las distancias de los caminos más cortos y el número de caminos más cortos para cada Node desde un vértice dado, S. Ejemplos: Entrada: S = 1, G = Salida: Las distancias de las rutas más cortas son: 0 … Continue reading «Número de rutas más cortas en un gráfico ponderado no dirigido»