Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

Tarefa de programação D:
algoritmo de Dijkstra

Escreva uma função caminho_minimo que receba um grafo g do SGB e dois de seus vértices, r e s, devolva um caminho de comprimento mínimo de r a s. O comprimento de um caminho é a soma dos comprimentos dos seus arcos. O comprimento de cada arco a é a->len. Sua função pode supor que o grafo não tem arcos de comprimento negativo.

O código de sua função deve ser extraído do módulo GB_DIJK do SGB:  elimine as partes irrelevantes do GB_DIJK mas preserve, tão fielmente quanto possível, as partes relevantes (pedaços de código, nomes das variáveis, utility fields, etc.)   Em particular, elimine

• a "heuristic function" (parâmetro hh) e
• o mecanismo que permite ao usuário fornecer sua própria implementação da fila-com-prioridade, que é a estruturas de dados mais importante do módulo.

O módulo oferece duas implementações de fila-com-prioridade (priority queue);  use a primeira.  (Mas a segunda implementação também é interessante e merece ser estudada!)

Documente corretamente sua função caminho_minimo e as eventuais funções auxiliares.