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 14
Hemos discutido las implementaciones de ruta más corta de Dijkstra.
- Algoritmo de Dijkstra para la representación de arrays de adyacencia (en C/C++ con complejidad temporal O(v 2 )
- Algoritmo de Dijkstra para la representación de listas de adyacencia (en C con complejidad temporal O (ELogV))
- Algoritmo de ruta más corta de Dijkstra usando set en STL (En C++ con Time Complexity O(ELogV))
La segunda implementación es mejor en cuanto a la complejidad del tiempo, pero es realmente compleja ya que hemos implementado nuestra propia cola de prioridad. La Tercera implementación es más simple ya que usa STL. El problema con la tercera implementación es que usa un conjunto que a su vez usa árboles de búsqueda binarios autoequilibrados. Para el algoritmo de Dijkstra, siempre se recomienda usar el montón (o cola de prioridad) ya que las operaciones requeridas (extraer mínimo y disminuir clave) coinciden con la especialidad del montón (o cola de prioridad). Sin embargo, el problema es que la prioridad_cola no admite la tecla de disminución. Para resolver este problema, no actualice una clave, pero inserte una copia más. Entonces permitimos múltiples instancias del mismo vértice en la cola de prioridad. Este enfoque no requiere una operación de tecla de disminución y tiene propiedades importantes a continuación.
- Cada vez que se reduce la distancia de un vértice, agregamos una instancia más de vértice en la cola_prioridad. Incluso si hay varias instancias, solo consideramos la instancia con la distancia mínima e ignoramos otras instancias.
- La complejidad del tiempo sigue siendo O(ELogV)) ya que habrá como máximo vértices O(E) en la cola de prioridad y O(Log E) es igual que O(Log V)
A continuación se muestra el algoritmo basado en la idea anterior.
1) Initialize distances of all vertices as infinite.
2) Create an empty priority_queue pq. Every item
of pq is a pair (weight, vertex). Weight (or
distance) is used as first item of pair
as first item is by default used to compare
two pairs
3) Insert source vertex into pq and make its
distance as 0.
4) While either pq doesn't become empty
a) Extract minimum distance vertex from pq.
Let the extracted vertex be u.
b) Loop through all adjacent of u and do
following for every vertex v.
// If there is a shorter path to v
// through u.
If dist[v] > dist[u] + weight(u, v)
(i) Update distance of v, i.e., do
dist[v] = dist[u] + weight(u, v)
(ii) Insert v into the pq (Even if v is
already there)
5) Print distance array dist[] to print all shortest
paths.
A continuación se muestra la implementación en C++ de la idea anterior.
CPP
// Program to find Dijkstra's shortest path using
// priority_queue in STL
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
// This class represents a directed graph using
// adjacency list representation
class Graph {
int V; // No. of vertices
// In a weighted graph, we need to store vertex
// and weight pair for every edge
list<pair<int, int> >* adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int u, int v, int w);
// prints shortest path from s
void shortestPath(int s);
};
// Allocates memory for adjacency list
Graph::Graph(int V)
{
this->V = V;
adj = new list<iPair>[V];
}
void Graph::addEdge(int u, int v, int w)
{
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
// Prints shortest paths from src to all other vertices
void Graph::shortestPath(int src)
{
// Create a priority queue to store vertices that
// are being preprocessed. This is weird syntax in C++.
// Refer below link for details of this syntax
// https://www.geeksforgeeks.org/implement-min-heap-using-stl/
priority_queue<iPair, vector<iPair>, greater<iPair> >
pq;
// Create a vector for distances and initialize all
// distances as infinite (INF)
vector<int> dist(V, INF);
// Insert source itself in priority queue and initialize
// its distance as 0.
pq.push(make_pair(0, src));
dist[src] = 0;
/* Looping till priority queue becomes empty (or all
distances are not finalized) */
while (!pq.empty()) {
// The first vertex in pair is the minimum distance
// vertex, extract it from priority queue.
// vertex label is stored in second of pair (it
// has to be done this way to keep the vertices
// sorted distance (distance must be first item
// in pair)
int u = pq.top().second;
pq.pop();
// 'i' is used to get all adjacent vertices of a
// vertex
list<pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i) {
// Get vertex label and weight of current
// adjacent of u.
int v = (*i).first;
int weight = (*i).second;
// If there is shorted path to v through u.
if (dist[v] > dist[u] + weight) {
// Updating distance of v
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
// Print shortest distances stored in dist[]
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
// Driver program to test methods of graph class
int main()
{
// create the graph given in above figure
int V = 9;
Graph g(V);
// making above shown graph
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.shortestPath(0);
return 0;
}
Producción
Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14
Una implementación más rápida utilizando el vector de representación de pares de gráfico ponderado :
CPP
// Program to find Dijkstra's shortest path using
// priority_queue in STL
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
// To add an edge
void addEdge(vector<pair<int, int> > adj[], int u, int v,
int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
// Prints shortest paths from src to all other vertices
void shortestPath(vector<pair<int, int> > adj[], int V,
int src)
{
// Create a priority queue to store vertices that
// are being preprocessed. This is weird syntax in C++.
// Refer below link for details of this syntax
// http://geeksquiz.com/implement-min-heap-using-stl/
priority_queue<iPair, vector<iPair>, greater<iPair> >
pq;
// Create a vector for distances and initialize all
// distances as infinite (INF)
vector<int> dist(V, INF);
// Insert source itself in priority queue and initialize
// its distance as 0.
pq.push(make_pair(0, src));
dist[src] = 0;
/* Looping till priority queue becomes empty (or all
distances are not finalized) */
while (!pq.empty()) {
// The first vertex in pair is the minimum distance
// vertex, extract it from priority queue.
// vertex label is stored in second of pair (it
// has to be done this way to keep the vertices
// sorted distance (distance must be first item
// in pair)
int u = pq.top().second;
pq.pop();
// Get all adjacent of u.
for (auto x : adj[u]) {
// Get vertex label and weight of current
// adjacent of u.
int v = x.first;
int weight = x.second;
// If there is shorted path to v through u.
if (dist[v] > dist[u] + weight) {
// Updating distance of v
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
// Print shortest distances stored in dist[]
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
// Driver program to test methods of graph class
int main()
{
int V = 9;
vector<iPair> adj[V];
// making above shown graph
addEdge(adj, 0, 1, 4);
addEdge(adj, 0, 7, 8);
addEdge(adj, 1, 2, 8);
addEdge(adj, 1, 7, 11);
addEdge(adj, 2, 3, 7);
addEdge(adj, 2, 8, 2);
addEdge(adj, 2, 5, 4);
addEdge(adj, 3, 4, 9);
addEdge(adj, 3, 5, 14);
addEdge(adj, 4, 5, 10);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 1);
addEdge(adj, 6, 8, 6);
addEdge(adj, 7, 8, 7);
shortestPath(adj, V, 0);
return 0;
}
Producción
Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
public class DijkstraAlgoForShortestDistance {
static class Node implements Comparable<Node> {
int v;
int distance;
public Node(int v, int distance)
{
this.v = v;
this.distance = distance;
}
@Override public int compareTo(Node n)
{
if (this.distance <= n.distance) {
return -1;
}
else {
return 1;
}
}
}
static int[] dijkstra(
int V,
ArrayList<ArrayList<ArrayList<Integer> > > adj,
int S)
{
boolean[] visited = new boolean[V];
HashMap<Integer, Node> map = new HashMap<>();
PriorityQueue<Node> q = new PriorityQueue<>();
map.put(S, new Node(S, 0));
q.add(new Node(S, 0));
while (!q.isEmpty()) {
Node n = q.poll();
int v = n.v;
int distance = n.distance;
visited[v] = true;
ArrayList<ArrayList<Integer> > adjList
= adj.get(v);
for (ArrayList<Integer> adjLink : adjList) {
if (visited[adjLink.get(0)] == false) {
if (!map.containsKey(adjLink.get(0))) {
map.put(
adjLink.get(0),
new Node(v,
distance
+ adjLink.get(1)));
}
else {
Node sn = map.get(adjLink.get(0));
if (distance + adjLink.get(1)
< sn.distance) {
sn.v = v;
sn.distance
= distance + adjLink.get(1);
}
}
q.add(new Node(adjLink.get(0),
distance
+ adjLink.get(1)));
}
}
}
int[] result = new int[V];
for (int i = 0; i < V; i++) {
result[i] = map.get(i).distance;
}
return result;
}
public static void main(String[] args)
{
ArrayList<ArrayList<ArrayList<Integer> > > adj
= new ArrayList<>();
HashMap<Integer, ArrayList<ArrayList<Integer> > >
map = new HashMap<>();
int V = 6;
int E = 5;
int[] u = { 0, 0, 1, 2, 4 };
int[] v = { 3, 5, 4, 5, 5 };
int[] w = { 9, 4, 4, 10, 3 };
for (int i = 0; i < E; i++) {
ArrayList<Integer> edge = new ArrayList<>();
edge.add(v[i]);
edge.add(w[i]);
ArrayList<ArrayList<Integer> > adjList;
if (!map.containsKey(u[i])) {
adjList = new ArrayList<>();
}
else {
adjList = map.get(u[i]);
}
adjList.add(edge);
map.put(u[i], adjList);
ArrayList<Integer> edge2 = new ArrayList<>();
edge2.add(u[i]);
edge2.add(w[i]);
ArrayList<ArrayList<Integer> > adjList2;
if (!map.containsKey(v[i])) {
adjList2 = new ArrayList<>();
}
else {
adjList2 = map.get(v[i]);
}
adjList2.add(edge2);
map.put(v[i], adjList2);
}
for (int i = 0; i < V; i++) {
if (map.containsKey(i)) {
adj.add(map.get(i));
}
else {
adj.add(null);
}
}
int S = 1;
// Input sample
//[0 [[3, 9], [5, 4]],
// 1 [[4, 4]],
// 2 [[5, 10]],
// 3 [[0, 9]],
// 4 [[1, 4], [5, 3]],
// 5 [[0, 4], [2, 10], [4, 3]]
//]
int[] result
= DijkstraAlgoForShortestDistance.dijkstra(
V, adj, S);
System.out.println(Arrays.toString(result));
}
}
Producción
[11, 0, 17, 20, 4, 7]
Optimización adicional Podemos usar una array de banderas para almacenar todos los vértices que se han extraído de la cola de prioridad. De esta forma podemos evitar la actualización de pesos de artículos que ya han sido extraídos. Consulte esto para una implementación optimizada. Este artículo es una contribución de Shubham Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA