Algoritmo de Dijkstra: Explicación y ejecución con el programa de C ++

Saber: ¿Cuál es de Dijkstra Algoritmo , por lo que se usa y cómo se llevarán a cabo utilizando un programa en C ++?

algoritmo de Dijkstra conocido como el algoritmo del camino más corto se utiliza para encontrar el camino más corto en un gráfico que cubre todos los vértices.

Dado un gráfico con el vértice de partida.

Algoritmo:

1. Inicialmente Dset contiene src
dist [s] = 0 dist [v] = ∞
2. Set Dset a vacío inicialmente
3. While todos los elementos en el gráfico no se agregan a ‘Dset’

A.	Let ‘u’ be any vertex not in ‘Dset’ and has minimum label    dist[u]
B. Add ‘u’ to Dset
C. Update the label of the elements adjacent to u
For each vertex ‘v’ adjacent to u
If ‘v’ is not in ‘Dset’ then
If dist[u]+weight(u,v)<dist[v] then
Dist[v]=dist[u]+weight(u,v)

¿Qué entendemos esto con la ayuda de un ejemplo:

Inicialmente Dset está vacío y la distancia de toda la vértices se establece a infinito, excepto la fuente de la que se establece en cero. En primer lugar nos encontramos con el vértice con distancia mínima. El vértice ‘A’ fue recogida, ya que es la fuente de actualización por lo Dset de Un .

Ahora actualizar la distancia de sus vértices adyacentes que B y C . Ahora encuentra el vértice cuya distancia es mínima, que es C .

Así actualizar Dset para C y actualizar la distancia de sus vértices adyacentes. Encuentra el vértice con la distancia mínima que es B .

actualización Dset para B y la distancia actualización de sus vértices adyacentes y luego encontrar el vértice con distancia mínima que es G .

actualización Dset de G y actualización a distancia de sus vértices adyacentes y encontrar el vértice con la distancia mínima que es E .

actualización Dset para E y la distancia de actualización de sus vértices adyacentes y encontrar el vértice con la distancia mínima que es F .

actualización Dset para F y actualización a distancia de sus vértices adyacentes y encontrar el vértice con distancia mínima que es D .

actualización Dset para D .

Como todos los vértices son parte de Dset así que conseguimos el camino más corto que contiene todos los vértices. Así que la gráfica de la ruta más corta desde el vértice Un es

Considere el programa:

#include<iostream>
#include<climits>
using namespace std;
#define vertex 7
int minimumDist(int dist[], bool Dset[])
{
int min=INT_MAX,index;
for(int v=0;v<vertex;v++)
{
if(Dset[v]==false && dist[v]<=min)
{
min=dist[v];
index=v;
}
}
return index;
}
void dijkstra(int graph[vertex][vertex],int src)
{
int dist[vertex];
bool Dset[vertex];
for(int i=0;i<vertex;i++)
{
dist[i]=INT_MAX;
Dset[i]=false;
}
dist[src]=0;
for(int c=0;c<vertex;c++)
{
int u=minimumDist(dist,Dset);
Dset[u]=true;
for(int v=0;v<vertex;v++)

{
if(!Dset[v] && graph[u][v] && dist[u]!=INT_MAX && dist[u]+graph[u][v]<dist[v])
dist[v]=dist[u]+graph[u][v];
}
}
cout<<"VertexttDistance from source"<<endl;
for(int i=0;i<vertex;i++)
{
char c=65+i;
cout<<c<<"tt"<<dist[i]<<endl;
}
}
int main()
{
int graph[vertex][vertex]={{0,5,3,0,0,0,0},{0,0,2,0,3,0,1},{0,0,0,7,7,0,0},{2,0,0,0,0,6,0},{0,0,0,2,0,1,0},{0,0,0,0,0,0,0},
{0,0,0,0,1,0,0}};
dijkstra(graph,0);
return 0;
}

salida

Vertex      Distance from source
A 0
B 5
C 3
D 9
E 7
F 8
G 6


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *