Existem vários algoritmos para se calcular o caminho mínimo de um vértice a outro em um grafo. Mas, com certeza, o mais famoso e mais utilizado por programadores, é o de Dijkstra.
Após escolher um vértice como raiz e outro como destino final, o algoritmo testa cada uma das arestas do grafo, somando seus pesos. No final, a menor soma é o menor caminho entre a raiz e o destino. O algoritmo pode ser usado sobre grafos orientados (dígrafos), ou não, e admite que todas as arestas possuem pesos não negativos (nulo é possível). Esta restrição é perfeitamente aceitável, por exemplo, no contexto de redes de transportes, onde as arestas representam normalmente distâncias ou tempos médios de percurso; poderão existir, no entanto, aplicações onde as arestas apresentam pesos negativos, nas quais o algoritmo não funcionará corretamente.
|
Esdger Dijkstra, o criador do algortimo
O cientista da computação Esdger Wybe Dijkstra (1930-2002) é natural de Roterdã na Holanda, e ficou conhecido mundialmente por suas contribuições na área de algoritmos e programas, linguagens de computação, sistemas operacionais e processamento distribuído.
Além de desenvolver o algoritmo de caminho mínimo mais famoso entre os programadores, algumas de suas principais contribuições foram o sistema operacional THE (SO construído em camadas e multitarefa) e a construção de semáforos (variáveis protegidas que tem a função de controlar o acesso a recursos compartilhados em um ambiente multitarefa). |
"Ciência da Computação está tão relacionada aos computadores quanto a Astronomia aos telescópios, Biologia aos microscópios, ou Química aos tubos de ensaio. A Ciência não estuda ferramentas. Ela estuda como nós as utilizamos, e o que descobrimos com elas."
Esdger Wybe Dijkstra
Cientista da Computação, criador do algoritmo de Dijkstra |
Nosso grupo implementou na aplicação "Grafo GDI" um algoritmo baseado no de Dijkstra, onde o caminho mínimo é calculado ignorando a direção das arestas. Enquanto o Algoritmo de Dijkstra calcula o caminho mínimo em grafos orientados ou não, nosso algoritmo calcula o caminho mínimo apenas em grafos não-orientados. A seguir, explicaremos passo-a-passo como funciona o algoritmo de Dijkstra.
Funcionamento do Algoritmo
Tomando como exemplo o grafo mostrado abaixo, começamos definindo qual será o vértice raiz. Neste caso, escolheremos o vértice s. A partir de agora o vértice s pode ser considerado como analisado, sua distância desde o vértice raiz é zero, pois ele próprio é o raiz, e não há anteriores a ele.
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
- |
- |
| v |
Não |
- |
- |
| x |
Não |
- |
- |
| y |
Não |
- |
- |
|
Depois, são analisados os vértices adjacentes, neste caso, u e x. E logo descobrimos que u está a distância 10 da raiz, e que x está a 5 dela.
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
10 |
s |
| v |
Não |
- |
- |
| x |
Não |
5 |
s |
| y |
Não |
- |
- |
|
O próximo passo é determinar as distâncias para outros vértices, a partir do que está a menor distância do vértice raiz (no caso x).
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
10 |
s |
| v |
Não |
- |
- |
| x |
Não |
5 |
s |
| y |
Não |
- |
- |
|
Assim, descobrimos 03 (três) arestas partindo de x para outros vértices. Atribuímos à tabela os valores dos mesmos. Perceba que a cada passo que o algoritmo dá, o valor dos vértices desconhecidos muda.
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
8 |
x |
| v |
Não |
14 |
x |
| x |
Sim |
5 |
s |
| y |
Não |
7 |
x |
|
Seguindo sempre a mesma linha de raciocínio, pegamos agora o próximo vértice que, dentro do grupo dos não-analisados, tem a menor distância do vértice raiz, sendo agora o vértice y.
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
8 |
x |
| v |
Não |
14 |
x |
| x |
Sim |
5 |
s |
| y |
Não |
7 |
x |
|
Descobrimos assim, uma aresta partindo de y para v, com peso 6, que faz com que a distância de v para a origem diminua de 14 para 13. Há também uma aresta apontando para a origem, mas como seu peso não irá produzir nenhuma mudança na tabela, a desconsideramos.
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
8 |
x |
| v |
Não |
13 |
y |
| x |
Sim |
5 |
s |
| y |
Não |
7 |
x |
|
Olhando para os vértices que ainda não foram analisados, vemos que o que tem a menor distância para o vértice raiz é u, sendo este o próximo a ser analisado.
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
8 |
x |
| v |
Não |
13 |
y |
| x |
Sim |
5 |
s |
| y |
Não |
7 |
x |
|
Analisando o vértice u, podemos constatar que há uma aresta apontando para o vértice v de peso 1. Perceba que agora, na tabela, a distância de v para a raiz diminui novamente, assim como seu antecessor.
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
8 |
x |
| v |
Não |
9 |
u |
| x |
Sim |
5 |
s |
| y |
Não |
7 |
x |
|
Resta agora analisarmos o último vértice, v
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
8 |
x |
| v |
Não |
9 |
u |
| x |
Sim |
5 |
s |
| y |
Não |
7 |
x |
|
Vemos apenas uma aresta apontando para y, que por não alterar em nada nossa tabela, pode ser desconsiderada.
 |
| Vértice |
Analisado? |
Dist |
Ant |
| s |
Sim |
0 |
- |
| u |
Não |
8 |
x |
| v |
Não |
9 |
u |
| x |
Sim |
5 |
s |
| y |
Não |
7 |
x |
|
Como todos os vértices foram analisados, nossa tabela está pronta, e nela está descrito com precisão o caminho mínimo para qualquer vértice do grafo, a partir do vértice raiz s.
