MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-078

Enunciado: Seja G o grafo com 5 nós e 7 arestas abaixo.

Para que valores dos pesos de arestas a, b e c (podendo ser negativos) o algoritmo de Dijkstra executado em G tendo o nó 1 como origem retorna distâncias corretas para todos os vértices?

A) a = 14, b = -6, c = 8;
B) a = 12, b = -4, c = 1;
C) a = 8, b = -5, c = 5;
D) a = 5, b = -6, c = 10;
E) NDA

Ideia original de: Félix Carvalho Rodrigues