Tiago Madeira

Grafos

Grafos Ponderados

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 0 a 3 não é a aresta 0–3, mas sim a aresta 0–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 \(\infty{}\) (infinito).

1 2 3 4 5
\(\infty\) \(\infty\) 3 5 \(\infty\) \(\infty\)
1 \(\infty\) \(\infty\) 2 \(\infty\) \(\infty\) \(\infty\)
2 3 2 \(\infty\) 1 \(\infty\) \(\infty\)
3 5 \(\infty\) 1 \(\infty\) \(\infty\) \(\infty\)
4 \(\infty\) \(\infty\) \(\infty\) \(\infty\) \(\infty\) 7
5 \(\infty\) \(\infty\) \(\infty\) \(\infty\) 7 \(\infty\)

Na verdade, só fazemos isso do infinito 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;
};

Comentários

Tiago Madeira » Grafos Ponderados

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

Tiago

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?

Tiago Madeira

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

Filipe Névola

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.

Filipe Névola

filipe.bico@hotmail.com

suely viana da silva

mandem exercicios resolvidos de algorítmo

Bebeto Damasceno

Muito bom, tirou minhas duvidas de forma simples e direta. Obrigado

Renan Gustavo

Tiago ficou excelente, bastante direto e com um exemplo fácil de entender. Agradeço.

Obrigado! Seu comentário foi enviado e será publicado quando for aprovado.

Infelizmente ocorreu um erro ao enviar seu comentário.