O algoritmo de Dijkstra para o problema do caminho mínimo em dígrafos com pesos utiliza uma fila de prioridades de vértices, na qual as prioridades...

O algoritmo de Dijkstra para o problema do caminho mínimo em dígrafos com pesos utiliza uma fila de prioridades de vértices, na qual as prioridades são uma estimativa do custo final. A cada iteração, um vértice é retirado da fila e os arcos que começam nesse vértice são analisados. Considere o seguinte grafo, no qual deseja-se conhecer o custo de um caminho mínimo para cada vértice, a partir do vértice D. Considere que -1 representa um custo 'infinito', ou seja,

A C 2
8 5 B
5 9 1 D E
5 1 3 1 F G 1

Com base nas informações e no grafo apresentados, assinale a alternativa que representa a estimativa de custo após duas iterações do algoritmo.


a) D: 0, E: 1, F: 4, G: 1
b) D: 0, E: 1, F: 3, G: 1
c) D: 0, E: 1, F: 3, G: 2
d) D: 0, E: 1, F: 4, G: 2