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

Criando efeitos em fotos no ASP.NET

Bom, sei que já escrevi esse artigo no linha de código e no código fonte, e também sei que não posto nada construtivo em meu blog faz tempo…  😉

por isso estou dando um copy+paste dele aqui em em blog!  ;P

Vamos lá….

O .Net possui uma excelente biblioteca para tratamento de imagens,  ela nos possibilita gerar efeitos,  recortes, desenhos  e etc, tudo através de uma “simples página asp.net.

Antigamente para criar efeitos em fotos precisavamos usar alguma IDE gráfica para depois publica-las na internet. Hoje podemos fazer isso on-line, sem perder tempo.

Neste momento você deve estar pensando, “isso deve ser algo MUITO DIFICIL!”

Mas acredite, não é!

Hoje teremos uma prova de como é fácil e simples brincar com fotos usando Dot.Net.

Para começar abra o Visual Studio, em seguida crie um projeto WebSite.

Em seu WebForm,  arraste 3 controles de imagem.

Defina uma imagem para o controle Image1.

Para o controle Image2 defina a ImageUrl como fotos.apx?tipo=negativo e para o controle Image3 defina a ImageUrl como fotos.apx?tipo=cinza

Exemplo:

<asp:Image ID=”Image1″ runat=”server”

ImageUrl=”foto.jpg” /><br />

<asp:Image ID=”Image2″ runat=”server”

ImageUrl=”fotos.aspx?tipo=negativo” /><br />

<asp:Image ID=”Image3″ runat=”server”

ImageUrl=”fotos.aspx?tipo=cinza” />


Acho que já deu para entender  o que vamos fazer mais adiante, certo? :-]

No .cs de sua página, adicione os namespaces System.Drawing e System.Drawing.Imaging em seguida crie o método Efeito. Este método possui a seguinte assinatura:

public void Efeito(string tipo)

Implementação:

public void Efeito(string tipo)

{

/*Aqui estamos definindo nossa imagem. Note que estamos carregando a imagem definida no Image1.
*No artigo gerando barras expliquei como funciona a classe Bitmap.*/

Bitmap bmp = new Bitmap(Server.MapPath(this.Image1.ImageUrl));

int x, y;

Byte RGB;

Color cor;

for (y = 0; y < bmp.Height; y++)

{

for (x = 0; x < bmp.Width; x++)

{

/*O metodo getPixel como o nome já diz,passa a cor do pixel nas posições de x,y.*/

cor = bmp.GetPixel(x, y);

RGB = cor.G;

/*Neste ponto escolhemos qual efeito usar. Lembrando que você pode criar seus próprios efeitos, basta modificar os valores do RGB.*/

if(tipo == “negativo”){

// Configuração para gerar o efeito de NEGATIVO

bmp.SetPixel(x, y,

Color.FromArgb(255, 255 – cor.R,

255 – cor.G, 255 – cor.B));

}

else

{

/* ajuste para gerar efeito cinza em sua foto! */

bmp.SetPixel(x, y, Color.FromArgb(RGB, RGB, RGB));

}

}

}

/* Neste ponto você informa ao browser que o documento enviado a ele, é uma imagem;*/

Response.ContentType = “image/jpeg”;

bmp.Save(Response.OutputStream,ImageFormat.Jpeg);

bmp.Dispose();

}

No Page_load de sua página adicione a instrução abaixo.

if(Request.QueryString[“tipo”] != null)

Efeito(Request.QueryString[“tipo”]);

O resultado será semelhante a imagem abaixo:

viu como a mágica acontece?  😉

[]’s

Animação com javascript puro em 45 linhas

Alguns dias atrás tirei 15 minutos de meu trabalho para fazer algo com um efeito de uma bola quicando em uma area definida no browser usando javascript ( não irei contar a verdadeira história que me levou a fazer isso, pois é algo longo…. 😛 ),  e como vi que ficou legal, achei bacana mostrar isso para vocês.

Espero que esse exemplo ajude alguém a ter novas ideias!  😉

Antes de colar o fonte + o link demo, quero dizer que somente testei esse efeito no Firefox e Chrome se alguém puder me da um feedback, ficarei feliz!  🙂

FONTE:

<script language=javascript>
var LIMITE_Y = 200,LIMITE_X = 200,LIMITE_BARRA = 0,DELAY = 10, VELOCIDADE = 2, X = 0, Y = 0;
var PAUSE = false;
var SENTIDO_Y = “D”, SENTIDO_X= “B”;
window.onload = function(){
var BOX = document.getElementById(“box”);
var BARRA = document.getElementById(“bloco”);
var AREA = document.getElementById(“area”);
BARRA.style.left = 75;
BARRA.style.top = 100;
BOX.style.left = X;
BOX.style.top = Y;
var LIMITE_BARRA_X = parseInt(BARRA.style.top.replace(“px”,””))-parseInt(BOX.offsetHeight)-parseInt(BARRA.offsetWidth);
var LIMITE_BARRA_Y = parseInt(BARRA.style.left.replace(“px”,””))+parseInt(BOX.offsetWidth);
window.setInterval(function() {
if(PAUSE) {
if (Y >= LIMITE_Y)SENTIDO_Y = “E”;
if (Y <= 0)SENTIDO_Y = “D”;
Y = (SENTIDO_Y == “D”) ? (Y+VELOCIDADE): (Y-VELOCIDADE);
if (X >= LIMITE_X)SENTIDO_X = “C”;
if (X <= 0)SENTIDO_X = “B”;
X = (SENTIDO_X == “B”) ? (X+VELOCIDADE) : (X-VELOCIDADE);
if((X == LIMITE_BARRA_X  && Y <= LIMITE_BARRA_Y)) SENTIDO_X = “C”;
if(X <= (LIMITE_BARRA_X+parseInt(BARRA.offsetWidth)+parseInt(BARRA.offsetHeight)) && Y <= parseInt(BOX.offsetHeight+BARRA.offsetHeight)) {
if(X == (LIMITE_BARRA_X+BARRA.offsetWidth+BARRA.offsetHeight))SENTIDO_Y = “E”;
else if (X > LIMITE_BARRA_X &&  X <= (parseInt(BOX.offsetHeight)+LIMITE_BARRA_X)){
SENTIDO_X = “B”;
SENTIDO_Y = “D”;
}
AREA.style.backgroundColor= (AREA.style.backgroundColor == ‘green’ ? ‘white’ : ‘green’);
}
BOX.style.left = Y;
BOX.style.top = X;
}
},DELAY);
}
</script>

 

var LIMITE_Y = 200,LIMITE_X = 200,LIMITE_BARRA = 0,DELAY = 10, VELOCIDADE = 2, X = 0, Y = 0;
var PAUSE = false;
var SENTIDO_Y = "D", SENTIDO_X= "B";
window.onload = function(){
var BOX = document.getElementById("box");
var BARRA = document.getElementById("bloco");
var AREA = document.getElementById("area");
BARRA.style.left = 75;
BARRA.style.top = 100;
BOX.style.left = X;
BOX.style.top = Y;
var LIMITE_BARRA_X = parseInt(BARRA.style.top.replace("px",""))-parseInt(BOX.offsetHeight)-parseInt(BARRA.offsetWidth);
var LIMITE_BARRA_Y = parseInt(BARRA.style.left.replace("px",""))+parseInt(BOX.offsetWidth);
window.setInterval(function() {
if(PAUSE) {
if (Y >= LIMITE_Y) SENTIDO_Y = "E";
if (Y <= 0) SENTIDO_Y = "D"; Y = (SENTIDO_Y == "D") ? (Y+VELOCIDADE): (Y-VELOCIDADE); if (X >= LIMITE_X) SENTIDO_X = "C";
if (X <= 0) SENTIDO_X = "B";
X = (SENTIDO_X == "B") ? (X+VELOCIDADE) : (X-VELOCIDADE);
if((X == LIMITE_BARRA_X && Y <= LIMITE_BARRA_Y)) SENTIDO_X = "C";
if(X <= (LIMITE_BARRA_X+parseInt(BARRA.offsetWidth)+parseInt(BARRA.offsetHeight)) && Y <= parseInt(BOX.offsetHeight+BARRA.offsetHeight)) { if(X == (LIMITE_BARRA_X+BARRA.offsetWidth+BARRA.offsetHeight))SENTIDO_Y = "E"; else if (X > LIMITE_BARRA_X && X <= (parseInt(BOX.offsetHeight)+LIMITE_BARRA_X)){
SENTIDO_X = "B";
SENTIDO_Y = "D";
}
AREA.style.backgroundColor= (AREA.style.backgroundColor == 'green' ? 'white' : 'green');
}
BOX.style.left = Y;
BOX.style.top = X;
}
},DELAY);
}

DEMO :   http://aspx.xmasters.com.br/bolinha/

Geração framework (qual é a sua opinião?)

Tenho notado que em fóruns,comunidades e até mesmo em chats, muitos programadores (“não todo, mas na sua grande maioria os novos programadores”) estão muito dependentes do uso de frameworks para seus desenvolvimentos.

Antes que pensem que estou aqui para pregar algo do tipo “morte aos frameworks”, quero deixar bem claro que uso e adoro usar alguns frameworks do mercado, sou usuário dos seguintes frameworks:
1 – Prototype (http://www.prototypejs.org/)
2 – Script.aculo.us (http://script.aculo.us/)
3 – JQuery (http://jquery.com/)

Entre outros…

O que está me deixando preocupado é que, geralmente quando ocorre algum problema com o framework, tais como:
1 – “Não atenda na solução do problema”
2 – ”Bugs encontrado”
3 – “Problemas em usar”

Muitos programadores não sabem como resolver ou não possuem conhecimento ou esperiência para resolver esses problemas.

Será que eles esqueceram ou não sabem como realmente as coisas funcionam por dentro do framework ?

Claro que ninguém é obrigado a saber tudo, mas acredito que o básico se faz necessário nessas horas…

Na empresa que trabalho, aconteceu algo muito parecido com a questão supracitada.

Lá existe um “Programa de Qualificação Profissional”, onde os estagiários passam por um ciclo de aprendizado ou treinamento para poder entrar na fabrica de software com uma base…

Pois bem….

Certo dia um dos estágiarios estava com muita dificuldade para usar alguns recursos do Javascript (sem framework). Para ajuda-lo chamei um programador que por sinal sabe tudo de jquery tanto nas coisas básicas quanto nas coisas avançadas
(criação de plugins para jquery, utilização de seletores avançados e etc..).

Para minha surpresa, ele teve uma grande dificuldade para ajudar o estagiário, o que me deu a entender é que de tanto usar frameworks, ele não sabia mais como usar o “javascript puro”…

Será que é seguro somente usar frameworks ?

Gostaria de saber a opinião de vocês…

PS: Sei que meu português é um pouco falho, se encontrar algum erro gramatical, não se espante!