Algoritmos Computacionais

Artigos sobre lógica de programação por Tiago Madeira

algoritmo: do Lat. algorithmos < Ár. alkharizmi: [Inform.] conjunto de etapas bem definidas necessárias para chegar à resolução de um problema.

Grafos Ponderados

January 26, 2006

Um grafo é ponderado quando suas arestas possuem um peso. O que significa isso? Bom... Vamos supor que eu queira ir de um lugar pra outro, mas o mais importante pra mim não seja a distância entre eles mas o pedágio que vou ter que pagar para pegar cada aresta (estrada). Nesse caso, o peso de cada aresta seria o custo que eu tenho pra passar pela estrada. O problema então seria calcular o caminho onde eu pago menos (o caminho que tem a menor soma de preços) e não o menor caminho no grafo "não-ponderado" (onde consideramos aresta=1 e nada=0).

Grafo Ponderado

Neste grafo, por exemplo, o menor caminho de 1 a 3 não é a aresta 1-3, mas sim a aresta 1-2 e depois a aresta 2-3.

Para representar um grafo ponderado, precisamos usar a matriz de adjacência, porque na lista de adjacência não temos como registrar o peso de cada aresta. Onde antes marcávamos "1", marcamos o peso que temos de ir de um vértice para o outro e onde marcávamos "0" marcamos $LaTeX: \infty{}$ (infinito)*.

	1	2	3	4
1	$LaTeX: \infty{}$	10	40	$LaTeX: \infty{}$
2	10	$LaTeX: \infty{}$	20	50
3	40	20	$LaTeX: \infty{}$	20
4	$LaTeX: \infty{}$	50	20	$LaTeX: \infty{}$

* Na verdade, só fazemos isso porque neste caso queremos o menor caminho e o 0 poderia atrapalhar, porque poderíamos ter um caminho sem pedágio, por exemplo.

E grafos ponderados são só isso. Não tem segredo. Na representação comum de grafos, você coloca o peso em cima ou do lado da aresta e pra representar na matriz de adjacências coloca o peso na posição matriz[v][w] (v e w são sempre vértices... v=vértice, w=próxima letra depois do v )

Mini-artigo... Ainda não entramos nos algoritmos e ainda não vamos entrar. Isso vai ficar pro próximo artigo: Busca em Profundidade. Espero que tenham gostado e qualquer coisa postem um comentário.

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais

Categoria(s): Grafos

5 comentários

#1 | Tiago Madeira » Grafos Ponderados (10/12/2006)

[…] O artigo está em outro local agora: Grafos ponderados […]

#2 | Tiago (23/06/2007)

Muito bom o artigo, simples e direto. É isso ae Tiago, parabéns por todos esse tópicos!!! Continue assim.

PS: A parte mais interessante, a dos algoritmos e buscas em grafos está demorando muito para sair. Vc tem alguma previsão?

#3 | Tiago Madeira (25/06/2007)

Vou tentar escrever sobre buscas em grafos até este final de semana. Informo-lhe por e-mail quando publicar.

#4 | Filipe Névola (15/06/2008)

Boa noite, gostaria de saber se você tem alguma implementação de menor caminho para me passar ??? Qualquer coisa entra em contato pelo meu e-mail. To começando a ver grafos para maratona e queria uma ajuda sua para resolver o G do aquecimento do IME do dia 14/06 (ontem) Obrigado.

#5 | Filipe Névola (15/06/2008)

filipe.bico@hotmail.com

Escreva um comentário

53 assinantes

Mais artigos

Comentários recentes

Matheus Eduardo Maura: Faço engenharia eletrica-eletronica( UNIRP SÃO JOSE DO RIO PRETO), e...
rafael: muito legal o artigo mas teria como resolver esse algoritmo nao consegui de jeito nenhum,...
Roger: Bom artigo. Podia atualizar esse site
Aline Celestrino Bento: o que É ALGORITMO=exemplo:35 :7 porque eu ñ sei ALINE
Claudio: eu gostaria de saber este algoritmo: faça um algoritmo que determine, para um digrafo,...
ingrid morgana gomes paes: que bacana que legau isso e emtesamte e legau para apremder mais a...
Filipe Névola: filipe.bico@hotmail. com
Filipe Névola: Boa noite, gostaria de saber se você tem alguma implementação de menor caminho...
Carlos Luiz Silva Meirelles: estou fazendo curso de informática gratuito patrocindo pelo estado....
Maria Regina de Queiroz: Olá Tiago, li os seus artigos e gostei muito, gostaria se possivel que...

Categorias

Escrevo também...

Tiago Madeira
Site pessoal e blog do autor destes artigos
Mal Vicioso
Blog sobre filosofia e sobre a hipocrisia da sociedade

Sobre o design

Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.

Licença

Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons.

HTML 4.01 gerado por WordPress em 0.438 segundos.