[Enunciado] Calcule uma CPT com origem a no grafo com custos nos arcos definido a seguir:
a-b b-c b-d d-c 1 2 3 -3
Veja os vetores pa[] e dist[] no início de sucessivas iterações do algoritmo de Dijkstra:
pa[] dist[]
a b c d a b c d
a - - - 0 - - -
a a - - 0 1 - -
a a b - 0 1 3 -
a a b b 0 1 3 4
O vetor dist[] produzido pelo algoritmo não dá as distâncias corretas a partir de a pois o arco d-c não está relaxado. Mais concretamente, o custo do caminho a-b-d-c é menor que dist[c].
Observe que o grafo não tem ciclos de custo negativo. Observe também não existe CPT nesse caso!