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

Como usar os Delegados (delegates) e Eventos no C#

 

Tenho percebido que para muitas pessoas o uso de Delegados e Eventos não está muito claro.

Bom então vamos á uma breve explicação sobre este assunto.

Em C# os delegados são objetos de primeira classe, totalmente suportados pela linguagem, um delegado é um tipo de referência usado para encapsular um método como uma assinatura e um tipo de retorno específico. Você pode encapsular QUALQUER método usando um delegate, mas o método deve coincidir com o delegate usado.

Criamos um delegado com a palavra-chave delegate seguida de um tipo de retorno e a assinatura dos métodos que podem ser delegados a ela, conforme abaixo:

public delegate int delegateInteiro();

Está declaração define um delegado chamado delegateInteiro, que encapsulará quaisquer método que retorne um inteiro.

Uma vez definindo o delegado, você pode encapsular um método-membro com ele, instanciando-o e passando um método que coincida com o tipo de assinatura.

Acho que já deu para termos uma idéia de como um delegate funciona, agora vamos falar um pouco sobre os Eventos.

Os eventos em C# são introduzidos junto com os delegados. Por convenção, os manipuladores de eventos do .NET Framework retornam void e recebem dois parâmetros. O primeiro parâmetro é a ‘fonte’ do evento (ou seja, o objeto que faz a públicação). O segundo parâmetro é um objeto derivado do EventArgs. É recomendável que seus manipuladores de eventos sigam esse padrão.

O EventArgs é a classe que serve de base para todos os dados de evento. A assinatura de um evento é parecido com este abaixo:

public event delegateInteiro eventoInteiro;

Bom agora vamos criar um programa que simula uma passagem de tempo, Ao iniciar nosso exercício, adicione o namespace System.Threading, com ele iremos simular um intervalo de tempo e ver os dias passarem como se fosse em um passe de mágica.

A estrutura de nossa aplicação ficará assim:

Abaixo estamos criando nossa classe de eventos, para ser usado posteriormente em nossa aplicação.

public class MeuEventArgs : EventArgs

{

public readonly int _dia;

public readonly int _mes;

public readonly int _ano;

public MeuEventArgs(int dia, int mes, int ano)

{

this._dia = dia;

this._mes = mes;

this._ano = ano;

}

}

Iremos criar uma Estrutura com DIA MÊS E ANO.

struct structData {

public int dia;

public int mes;

public int ano;

}

Para podermos gerar nossa passagem de tempo, vamos implementar a classe que realmente fará isso.

public class PassagemDeTempo

{

// Note que estamos iniciando o mes com o valor 11 e o ano com o valor 1900.

private int _dia;

private int _mes = 11;

private int _ano = 1900;

private structData _data = new structData();

// Declaramos nosso delegado para encapsular os metodos.

public delegate void PassagemDeTempoHandler(object sender, MeuEventArgs e);

// Nosso evento, onde passaremos nosso delegado com seu método encapsulado.

public event PassagemDeTempoHandler OnPassagemDeTempo;

// Iniciando a passagem de tempo.

public void IniciarPassagem() {

for (;;)

{

// Aqui estamos dando um intervalo de ½ seg. para podermos ver essa passagem

Thread.Sleep(500);

// Gerando os dias,meses e anos e abastecendo nossa estrutura

_data.mes = gerarMes(_mes);

_data.dia = gerarDias(_dia);

_data.ano = gerarAno(_ano);

Sempre que passar um dia chamaremos nosso evento.

if (_data.dia != _dia)

{

MeuEventArgs eve = new MeuEventArgs(_data.dia, _data.mes, _data.ano);

if (OnPassagemDeTempo != null)

{

OnPassagemDeTempo(this, eve);

}

}

this._dia = _data.dia;

this._mes = _data.mes;

this._ano = _data.ano;

}

}

// os metodos abaixo são apenas tratamentos.

private int gerarDias(int dia){

if (dia >= 31) return 1;

return ++dia;

}

private int gerarMes(int mes){

if (_dia >= 31)

{

if (mes >= 12) return 1;

return ++mes;

}

else

return mes;

}

public int gerarAno(int ano) {

if (_mes == 12 && _dia == 31)

return ++ano;

else

return ano;

}

}

// Aqui em nossa classe MostrarPassagemDeTempo que exibimos os dias passando.

public class MostrarPassagemDeTempo

{

public void Subscribers(PassagemDeTempo _tempo)

{

//Arqui estamos encapsulando a funcao que mostra a passagem de tempo.

// note que estamos abastecendo um evento.

_tempo.OnPassagemDeTempo += new PassagemDeTempo.PassagemDeTempoHandler(Mostrar);

}

public void Mostrar(object sender,MeuEventArgs e)

{

Console.WriteLine(“{0}/{1}/{2}”, e._dia, e._mes, e._ano);

}

}

}

Para finalizar em nosso MAIN apenas escreveremos 4 linha de código:

PassagemDeTempo PassTmp = new PassagemDeTempo();

MostrarPassagemDeTempo MosPassTmp = new MostrarPassagemDeTempo();

MosPassTmp.Subscribers(PassTmp);

PassTmp.IniciarPassagem();

Ao executar está aplicação veremos o seguinte resultado.

 

 

 

Desculpa para aprender? [POST RÁPIDO]

Uma lista bem legal…

For C Tutorials.
http://www.codevdo.com/Languages/C
For C++ Tutorials.
http://www.codevdo.com/Languages/CPP
For C#.NET Tutorials.
http://www.codevdo.com/Languages/CSharp_Dotnet
For VB.NET Tutorials.
http://www.codevdo.com/Languages/VB_Dotnet
For Java Tutorials.
http://www.codevdo.com/Languages/Java
For Perl Tutorials.
http://www.codevdo.com/Languages/Perl
For MS Access Tutorials.
http://www.codevdo.com/Database/Ms_Access
For SQL Server Tutorials.
http://www.codevdo.com/Database/SQL_Server
For MySQL Tutorials.
http://www.codevdo.com/Database/MySQL
For Oracle Tutorials.
http://www.codevdo.com/Database/Oracle
For iPhone Apps Tutorials.
http://www.codevdo.com/Mobile/iPhone_Apps
For Android Apps Tutorials.
http://www.codevdo.com/Mobile/Android_Apps
For HTML/DHTML Tutorials.
http://www.codevdo.com/Web/HTML_DHTML
For jQuery Tutorials.
http://www.codevdo.com/Web/jQuery
For PHP Tutorials.
http://www.codevdo.com/Web/PHP

Uma simplória analogia entre caverna do dragão e uma empresa de desenvolvimento de sistemas.

( Empresa de desenvolvimento de sistemas = Caverna do Dragão )

O escritório geralmente fica num lugar longe pra caramba, cheio de perigos para chegar (Marginal Tietê, enchente, trânsito), onde você nunca sabe como chegou e tem que penar para sair. Na verdade quando você entrou nele parecia um parque de diversão, mas na verdade é o lugar onde você vai passar por todo tipo de perrengue antes de voltar pra casa!

Gerente de TI = Mestre dos Magos: Responsável por te colocar nas maiores enrascadas, sempre aparece do nada, pergunta umas paradas nada a ver, não tem reposta para nenhuma de suas perguntas, nunca ajuda e por ele você não sai nunca da Caverna do Dragão. Dizem que ele tem um poder e conhecimento ilimitado, mas você nunca vai ver em utilização. Se é que é verdade mesmo.

Suporte Técnico = Uni: Só faz volume no grupo, não tem nenhuma habilidade especial, não sabe falar (nem escrever), precisa ser salva a toda hora colocando a equipe toda em perigo. Na verdade ninguém sabe porque ela está na party, e sempre tem um que quer se sacrificar para ajudá-la. E no final, a party nunca vai embora sem a Uni!


Gerência de Projeto (PMO) = Vingador:
Como se não bastasse o Mestre dos Magos para encher o saco, o Vingador (que não tem nada a ver com você ou com seus problemas) vem toda hora te torrar a paciência, aumentando suas tarefas (ou enrascadas) e tentando te aterrorizar com prazos e atividades que você não pode cumprir. Na verdade a função principal dele ninguém sabe direito, mas é um dos seres mais temidos da Caverna do Dragão, que sempre aparece na hora errada e quando aparece você sabe que vem encrenca.


Equipe de Manutenção = Eric, Diana e Presto:
Tem um que sempre quer se defender de tudo quanto é bucha (com o escudo) e está sempre reclamando por isso, outro que é obrigado a fazer mágica para cumprir a demanda (com o chapéu), e no final todo mundo acaba tendo que pular todos os processos (com o bastão) para o sistema voltar a funcionar..


Equipe Desenvolvimento = Hank, Sheila e Bobby:
Sempre precisa conseguir fazer qualquer coisa (arma, defesa, corda, rede, programa em três camadas) com apenas um arco e flecha e tem sempre um novato que vem e acaba quebrando tudo o que funcionava perfeitamente (com o tacape). E a Sheila? Digamos que sempre tem um que desaparece quando mais se precisa.

Cliente = Tiamat: No fundo, só quer ter um pouco de sossego. É gigante e poderoso. A Uni (suporte) acha que ele vai  comê-la, por isso se caga de medo e perde a voz perto dele, o Vingador (PMO) que se acha o maioral, também treme na base e acaba cedendo a tudo o que ele pede, o Mestre dos Magos (Gerente) não ajuda em nada mesmo, só fica perguntando coisas sem sentido e some quando se precisa dele, e sempre sobra para a party (Manutenção e Desenvolvimento) se f*#% para vencê-lo a qualquer custo. E depois, com todo mundo cansado e sem paciência, o Mestre dos Magos e o Vingador voltam para trazer mais um desafio antes de te deixar voltar para casa.

enviado por Domingos de paola

GCTS – Gambi Certified Technology Specialist

Com o crescimento de novos tipos de gambiarras em meados de 2008 a Microsoft realizou também alterações em seu modelo de certificação. Visando esse público foi criado o GCTS – Gambi Certified Technology Specialist.
A certificação GCTS – é o nível mais básico de certificação entre as novas certificações.
Com esta certificação o profissional comprova seu conhecimento específico em desenvolvimento de POG ( programação orientado a gambiarra) e POT (programação orientada a trambique).
Abaixo temos um exemplo do certificado GCTS:


*Para os que não sabem o que é POT ou  POG,  aguarde…

Faculty Connection Experience com novo conteúdo para professores

Faculty Connection

A área acadêmica da Microsoft disponibiliza aos professores de todo o Brasil um conjunto de vídeos com aulas conceituais sobre as tecnologias Microsoft. Este conteúdo pode ser usado pelo professor para complementar a teoria apresentada em sala de aula. A maior parte destes vídeos foi desenvolvido por professores de renomadas instituições, como USP e UNESP. A lista completa dos cursos está disponível no Faculty Connection Experience!