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).
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 usando a matriz de adjacência, 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 
(infinito)*.
| 1 | 2 | 3 | 4 | |
| 1 | |
10 | 40 | |
| 2 | 10 | |
20 | 50 |
| 3 | 40 | 20 | |
20 |
| 4 | |
50 | 20 | |
* Na verdade, só fazemos isso porque neste caso iríamos querer o menor caminho e o 0 poderia atrapalhar, porque poderíamos ter um caminho sem pedágio, por exemplo, mas isso sempre depende do caso.
Usando listas de adjacência, podemos representar as ligações de cada vértice com dois vetores (um para dizer a qual ele se liga e outro o peso desta ligação) ou com um vetor de structs como:
struct edge { int destino, peso;};
5 comentários
[...] O artigo está em outro local agora: Grafos ponderados [...]
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?
Vou tentar escrever sobre buscas em grafos até este final de semana. Informo-lhe por e-mail quando publicar.
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.
Escreva um comentário
Para ler o que escrevo atualmente, visite meu novo blog.
Índice
- Crivo de Eratóstenes
- Escada perfeita (OBI2006)
- Grafos Ponderados
- Representando Grafos na Programação
- Os Grafos e o Orkut
- Mini-Poker
- Ordenação por Seleção
- Ordenação por Inserção
- Introdução à Ordenação de Vetores
- Recursão
- Análise de Algoritmos
- Qual a utilidade do algoritmo?
- Como representar um algoritmo?
- O que é um algoritmo?
Online Judges
Programming Contests
- ACM International Collegiate Programming Contest
- Maratona de Programação da SBC
- Olimpíada Brasileira de Informática
- International Olympiad in Informatics
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 que permite que você copie, distribua, exiba, execute a obra e crie obras derivadas desde que mantenha os créditos, não use sua modificação para fins comerciais e compartilhe seu trabalho derivado pela mesma licença.