Shortest Paths (caminhos mínimos) Simples e direto…

Quando se fala de algoritmos de caminho mínimo o nome Edsger Dijkstra é sempre evidenciado.

Este algoritmo é capaz de determinar o caminho mínimo, partindo de um vértice de inicio para todos os outros vértices de um grafo.

O algoritmo leva o tempo O(m + n log n) caso seja usado um HEAP DE FIBONACCI , O(m log n)  caso seja usado um HEAP BINÁRIO e O(n²) caso seja usado um vetor para armazenar Q.

O Problema de caminhos mínimos se propõe em reduzir o excesso de travessias de um grafo entre dois vértices.

Essa redução é proposta pela soma dos pesos de cada aresta percorrida. Mediante a isso é dado um conjunto V de vértices e um, outro conjunto A de arestas  que por sua vez possui um peso entre  a ligação de dois  vértices.
Com essas informações é aplicado a fórmula:

f1
Onde dado qualquer valor de V será encontrado um caminho para P de, tal  que  f2é o menor caminho.

O caminho mínimo entre D e E não D-E, mas sim  D-F-E, com uma distância de 14.
f3

 

 

 

 

 

Usaremos o algoritmo de Dijkstra para descobrir o menor caminho entre duas estações de trem.

t1

 

 

 

 

 

 

 

 

 

 

Cada estação é um vértice e as ligações entre duas ou mais estações são nossas arestas com seus  respectivos pesos.

Quando Informamos uma origem e um destino  o programa nos dará o melhor/menor caminho do ponto A ao ponto B.

Em nosso exemplo o menor caminho entre a estação de  Manguinhos e Campo Grande  é a sinalizada em vermelho.

t2

 

 

 

 

 

 

 

 

 

 

 

 

Código fonte.

 

Modelos

public class Vertice
{
public string Id{get;set;}
public string Nome{get;set;}
public Point XY{get;set;}
public bool EhTerminal{get;set;}
public Vertice(string id, string nome, Point xy, bool ehTerminal = false)
{
Id = id;
Nome = nome;
XY = xy;
EhTerminal = ehTerminal;
}
}
public class Grafo
{
public List<Vertice> Vertices{get;set;}
public List<Aresta> Arestas{get;set;}
public Grafo(List<Vertice> vertices, List<Aresta> arestas)
{
Arestas = arestas;
Vertices = vertices;
}
}
public class Aresta
{
public string Id { get; set; }
public Vertice Origem { get; set; }
public Vertice Destino { get; set; }
  /// <summary>
        /// Calculo de distância entre Vértice A e Vértice B.
        /// </summary>
public int Peso
{
get
{
double x1 = Origem.XY.X, y1 = Origem.XY.Y;
double x2 = Destino.XY.X, y2 = Destino.XY.Y;
double peso = Math.Sqrt(Math.Pow(x2 – x1, 2.0) + Math.Pow(y2 – y1, 2.0));
return Convert.ToInt32(peso);
}
}
public Aresta(string id, Vertice origem, Vertice destino)
{
Id = id;
Origem = origem;
Destino = destino;
}
}

 

Algoritmo

public class Dijkstra
{
public List<Vertice> Vertices{get;set;}
public List<Aresta> Arestas{get;set;}
public HashSet<Vertice> VerticesVerificados{get;set;}
public HashSet<Vertice> VerticesNaoVerificados{get;set;}
public Dictionary<Vertice, Vertice> Predecessores{get;set;}
public Dictionary<Vertice, int> Distancia{get;set;}
public Dijkstra(Grafo grafo)
{
Vertices = new List<Vertice>(grafo.Vertices);
Arestas = new List<Aresta>(grafo.Arestas);
}
public void Executar(Vertice origem)
{
VerticesVerificados = new HashSet<Vertice>();
VerticesNaoVerificados = new HashSet<Vertice>();
Distancia = new Dictionary<Vertice, int>();
Predecessores = new Dictionary<Vertice, Vertice>();
Distancia.Add(origem, 0);
VerticesNaoVerificados.Add(origem);
while (VerticesNaoVerificados.Count() > 0)
{
Vertice vertice = MenorCaminho(VerticesNaoVerificados);
VerticesVerificados.Add(vertice);
VerticesNaoVerificados.Remove(vertice);
BuscarMenorDistancia(vertice);
}
}

private void BuscarMenorDistancia(Vertice vertice)
{
List<Vertice> VerticesAdjacentes = RetornarVizinhos(vertice);
foreach (Vertice adjacente in VerticesAdjacentes)
{
if (
RetornarMenorDistancia(adjacente) >
RetornarMenorDistancia(vertice) +
RetornarDistancia(vertice, adjacente))
{
if (Distancia.ContainsKey(adjacente))
Distancia[adjacente] = RetornarMenorDistancia(vertice) +
RetornarDistancia(vertice, adjacente);
else    Distancia.Add(adjacente, RetornarMenorDistancia(vertice) +
RetornarDistancia(vertice, adjacente));
if (Predecessores.ContainsKey(adjacente))
Predecessores[adjacente] = vertice;
else Predecessores.Add(adjacente, vertice);

VerticesNaoVerificados.Add(adjacente);
}
}
}

private int RetornarDistancia(Vertice vertice, Vertice adjacente)
{
foreach (Aresta aresta in Arestas)
{
if (aresta.Origem.Equals(vertice) &&
aresta.Destino.Equals(adjacente))
{
return aresta.Peso;
}
}
return int.MaxValue;
}

private List<Vertice> RetornarVizinhos(Vertice vertice)
{
List<Vertice> vizinhos = new List<Vertice>();
foreach (Aresta aresta in Arestas)
{
if (aresta.Origem.Equals(vertice) &&
!JahVerificado(aresta.Destino))
{
vizinhos.Add(aresta.Destino);
}
}
return vizinhos;
}

private bool JahVerificado(Vertice vertice)
{
return VerticesVerificados.Contains(vertice);
}

private Vertice MenorCaminho(HashSet<Vertice> vertices)
{
Vertice menorVertice = null;
foreach (Vertice vertice in vertices)
{
if (menorVertice == null)
menorVertice = vertice;
else if (RetornarMenorDistancia(vertice) < RetornarMenorDistancia(menorVertice))
menorVertice = vertice;
}
return menorVertice;
}

private int RetornarMenorDistancia(Vertice destino)
{
int distancia = Distancia.ContainsKey(destino) ? Distancia[destino] : -1;
if (distancia == -1)
return int.MaxValue;
return distancia;
}

public List<Vertice> RetornarCaminho(Vertice vertice)
{
List<Vertice> caminho = new List<Vertice>();
Vertice passo = vertice;
if (!Predecessores.ContainsKey(passo))
return null;
caminho.Add(passo);
while (Predecessores.ContainsKey(passo))
{
passo = Predecessores.ContainsKey(passo) ? Predecessores[passo] : null;
caminho.Add(passo);
}
caminho.Reverse();
return caminho;
}
}

Codigo fonte completo:  Algoritmo de Dijkstra

Fonte:

http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html

http://www.codeproject.com/Articles/24816/A-Fast-Priority-Queue-Implementation-of-the-Dijkst

http://www.codeproject.com/Articles/19919/Shortest-Path-Problem-Dijkstra-s-Algorithm

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

 

Anúncios

Systems Analyst / .Net Developer

Marcado com: , , , , ,
Publicado em Zoações...

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: