Primero explicaré el algoritmo
El algoritmo que vamos a utilizar para determinar la ruta más corta se llama “algoritmo de Dijkstra”. El algoritmo de Dijkstra es un algoritmo iterativo que nos proporciona la ruta más corta desde un nodo inicial en particular a todos los demás nodos en el gráfico. Nuevamente, esto es similar a los resultados de una primera búsqueda amplia.
Para realizar un seguimiento del costo total desde el nodo de inicio hasta cada destino, utilizaremos la variable de distinción en la clase Vertex. La variable de instancia dist contendrá el peso total actual de la ruta de peso más pequeña desde el inicio hasta el vértice en cuestión. El algoritmo itera una vez por cada vértice en el gráfico; sin embargo, el orden en que iteramos sobre los vértices está controlado por una cola de prioridad. El valor que se utiliza para determinar el orden de los objetos en la cola de prioridad es dist. Cuando se crea un vértice por primera vez, dist se establece en un número muy grande. Teóricamente, establecería dist en infinito, pero en la práctica simplemente lo establecemos en un número que es mayor que cualquier distancia real que tendríamos en el problema que estamos tratando de resolver.
El algoritmo de Dijkstra usa una cola prioritaria. Puede recordar que una cola prioritaria se basa en el montón que implementamos en el Capítulo del árbol. Hay un par de diferencias entre esa implementación simple y la implementación que usamos para el algoritmo de Dijkstra. Primero, la clase PriorityQueue almacena tuplas de pares clave, valor. Esto es importante para el algoritmo de Dijkstra ya que la clave en la cola de prioridad debe coincidir con la clave del vértice en el gráfico. En segundo lugar, el valor se utiliza para decidir la prioridad y, por lo tanto, la posición de la clave en la cola de prioridad. En esta implementación, usamos la distancia al vértice como prioridad porque, como veremos cuando exploremos el próximo vértice, siempre queremos explorar el vértice que tiene la menor distancia. La segunda diferencia es la adición del método decreciente. Como puede ver, este método se usa cuando la distancia a un vértice que ya está en la cola se reduce y, por lo tanto, mueve ese vértice hacia el frente de la cola.
Ahora tomaré un ejemplo de un problema del Juez Esfera en línea (SPOJ)
SPOJ.com – Problema EZDIJKST
- ¿Los comerciantes algorítmicos institucionales necesitan tener una sólida comprensión de la microestructura del mercado?
- ¿Cómo hacemos análisis de búsqueda binaria (matriz)?
- ¿Cuál es la diferencia entre el orden de fusión de arriba hacia abajo y el de fusión de abajo hacia arriba?
- ¿Cómo funciona la transformación cuántica de Fourier?
- ¿Cuál sería el algoritmo para encontrar subárboles duplicados en un árbol binario?
#include #include #include using namespace std; #define pp pair using namespace std; const int INF=INT_MAX; class Prioritize { public: int operator() ( const pair& p1, const pair& p2 ) { return p1.second >tc; while(tc--) { priority_queue<pp, vector, Prioritize> Q; scanf("%d%d",&node,&edges); vector G[node+1]; for(int i=0;i<edges;i++) { scanf("%d%d%d",&a,&b,&w); G[a].push_back(pp(b,w)); } int s,d; int dis[node+1]; for(int i=1;i<=node;i++) { dis[i] = INT_MAX; } scanf("%d%d",&s,&d); dis[s]=0; Q.push(pp(s,dis[s])); while(!Q.empty()) { a = Q.top().first; Q.pop(); int size = G[a].size(); for(int i=0;i dis[a]+ w) { dis[b] = dis[a]+w; Q.push(pp(b,dis[b])); } } } if(dis[d]==INF) puts("NO"); else printf("%d\n",dis[d]); } } 
