Algoritmo de Dijkstra para determinar a
distância entre os vertices a e z de um grafo não dirigido com pesos
Dado um grafo com pesos, considera-se que
(
p(x, y) =
peso da aresta {x, y}, se {x, y} é uma aresta do grafo;
∞, caso contrário
O Algoritmo de Dijkstra para determinar a
distância entre os vértices a e z é descrito a seguir:
1.
2.
3.
4.
5.
6.
7.
8.
9.
L(a) := 0
L(x) := ∞, x 6= a
S := ∅
Se z ∈ S, vai-se para 9.; se z ∈
/ S, continua-se em 5.
Escolhe-se um vértice v tal que L(v) = minx6∈S L(x)
S := S ∪ {v}
L(x) := min{L(x), L(v) + p(v, x)} para todo o vértice x
Vai para 4.
L(z) = distância de a a z
Se além da distância, pretendemos a árvore correspondente a um caminho
mais curto de a para z, podemos juntar ao algoritmo a construção dessa árvore
T , onde os vértices de T são os elementos de S e as arestas são aquelas cujo
peso entra no cálculo do mı́nimo referido no passo 5. Na resolução do exercı́cio
30 da Ficha Teórico-Prática 5, a seguir, introduzem-se os passos 30 e 60 onde se
constrói o conjunto R constituı́do pelas arestas de T :
Resolução do exercı́cio 30
1. L(A) := 0
2. L(X) := ∞, X 6= A
3. S := ∅
30 . R := ∅
4. G ∈
/S
5. L(A) = minX∈S L(X)
6. S := S ∪ {A} = {A}
60 . R := R ∪ ∅ = ∅
7. L(X) := min{L(X), L(A) + p(A, X)}; logo L(B) = min{∞, 3} = 3,
L(C) = min{∞, 6} = 6, L(X) = ∞ para X 6= A, B, C
1
4. G ∈
/S
5. L(B) = minX∈S L(X) = 3
6. S := S ∪ {B} = {A, B}
60 . R := R ∪ {{A, B}} = {{A, B}}
7. L(X) := min{L(X), L(B) + p(B, X)}; logo L(C) = min{6, 3 + 2} = 5,
L(D) = min{∞, 3 + 4} = 7, L(X) = ∞ para X 6= A, B, C, D
4. G ∈
/S
5. L(C) = minX∈S L(X) = L(B) + p(B, C) = 5
6. S := S ∪ {C} = {A, B, C}
60 . R := R ∪ {{B, C}} = {{A, B}, {B, C}}
7. L(X) := min{L(X), L(C) + p(C, X)}; logo L(D) = min{7, 5 + 1} = 6,
L(E) = min{∞, 5 + 4} = 9, L(F ) = min{∞, 5 + 2} = 7, L(G) = ∞
4. G ∈
/S
5. L(D) = minX∈S L(X) = L(C) + p(C, D) = 6
6. S := S ∪ {D} = {A, B, C, D}
60 . R := R ∪ {{C, D}} = {{A, B}, {B, C}, {C, D}}
7. L(X) := min{L(X), L(D) + p(D, X)}; logo L(G) = min{∞, 10} = 10,
L(E) = min{9, 6 + 2} = 8 e L(F ) = 7 = L(C) + p(C, F )
4. G ∈
/S
5. 5. L(F ) = minX∈S L(X) = L(C) + p(C, F ) = 7
6. S := S ∪ {F } = {A, B, C, D, F }
60 . R := R ∪ {{C, F }} = {{A, B}, {B, C}, {C, D}, {C, F }}
7. L(X) := min{L(X), L(F ) + p(F, X)}; logo L(G) := min{10, 7 + 1} = 8 e
L(E) := min{8, 7 + 1} = 8
/S
4. G ∈
5. L(E) = minX6∈S L(X) = 8 = L(D) + p(D, F )
6. S := S ∪ {E} = {A, B, C, D, E, F }
60 . R := R ∪ {{D, F }} = {{A, B}, {B, C}, {C, D}, {C, F }, {D, F }}
2
7. L(X) := min{L(X), L(E) + p(E, X)}; logo L(G) = min{8, 8 + 1} = 8 =
L(F ) + p(F, G)
4. G ∈
/S
5. L(G) = minX6∈S L(X) = L(F ) + p(F, G) = 8
6. S := S ∪ {G} = {A, B, C, D, E, F, G}
60 . R := R ∪ {{F, G}} = {{A, B}, {B, C}, {C, D}, {C, F }, {D, F }, {F, G}}
9. L(G)=distância de A a G.
A árvore T = (S, R) = ({A, B, C, D, E, F, G}, {{A, B}, {B, C}, {C, D}, {C, F }, {D, F }, {F, G}})
dá um caminho mais curto no grafo dado de A para cada um dos vértices pertencentes à árvore. Assim um caminho mais curto de A a G é < A, B, C, F, G >.
3