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 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).

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;
};

No primeiro artigo desta série, o Hélio comentou: ‘Algoritmos’ é um tema pouco valorizado por muitos programadores iniciantes, que querem logo botar a mão na massa.

É a mais pura verdade. Quando eu tive a minha primeira noção do que são algoritmos (no dia 12 de julho de 2004, no Curso de Programação da Olimpíada Brasileira de Informática na UNICAMP), confesso que fiquei decepcionado. Qual a utilidade de algo tão formal pra algo que já sabemos fazer? Eu já programava em C e achei um saco o professor escrevendo no quadro aqueles pseudocódigos de problemas super simples, perdendo tempo com isso ao invés de programar. Porém, hoje percebo que algoritmos são muito mais legais (e importantes) do que eu pensava. Claro que para somar dois inteiros não há necessidade de escrever um pseudocódigo, mas algoritmos são representações essenciais para problemas mais complexos e grandes aplicações.

Acredito que você que já leu os dois primeiros artigos já deve saber, mas não custa lembrar: algoritmo é a relação entre entrada e saída do programa, é o rascunho do programa, o projeto. E um projeto antes de colocar a mão na massa é indispensável. Enquanto a implementação é a função dos pedreiros, o algoritmo é a função dos engenheiros. Se os engenheiros não existissem, acho que os pedreiros não iam conseguir fazer as casas e os prédios que eles constroem hoje em dia!

Não querendo desmerecer alunos de sistemas de informação, mas a maioria deles não passa de pedreiros.

O algoritmo sempre existe, mesmo que apenas no seu pensamento. A primeira coisa que você pensa quando quer fazer uma aplicação (a não ser que você seja louco) é: o que é a aplicação? O que ela vai fazer? E se você sair implementando uma coisa complexa, você vai se decepcionar depois demorando mais do que o tempo de fazer a implementação só para limpar o código! Por isso, representar algoritmos complexos é essencial.

E mais… Mesmo se você tivesse tempo infinito, memória infinita, etc. e tal (não tivesse necessidade de limpar o código), você vai precisar de um algoritmo pra provar que o seu programa funciona, para se organizar e para estudar a sua lógica. Se você não planejar um algoritmo para o caso acima, qualquer funcionalidade que você queira adicionar no meio, por falta de projeto e organização, vai demorar bem mais tempo. Por isso, algoritmo não é uma perda de tempo antes da programação, mas a programação é que se torna uma perda de tempo quando não teve um algoritmo (ou, um projeto). O livro Algoritmos: Teoria e Prática reforça essa interessante idéia na página 7:

Suponha que os computadores fossem infinitamente rápidos e que a memória do computador fosse livre. Você teria alguma razão para estudar algoritmos? A resposta é sim, se não por outra razão, pelo menos porque você ainda gostaria de demonstrar que o método da sua solução termina, e o faz com a resposta certa.

Outra utilidade do algoritmo é compartilhar idéias de problemas complexos. Todo programador entende um pseudocódigo e por isso convém muitas vezes apresentar sua idéia de um programa em forma de um algoritmo, num pseudocódigo, ao invés de passar um programa implementado em C para uma dúzia de programadores de VBScript (e sem dúvidas é muito melhor do que ter que aprender uma linguagem da Microsoft!!!).

Existe uma série de algoritmos comuns que todo programador deve conhecer (projetos prontos para muitas coisas complicadas que precisamos implementar no dia-a-dia) e isso é o que vamos começar a estudar no próximo artigo. :)