Projeto e Análise de Algoritmos - Algoritmos em Grafos (parte 2)

Prévia do material em texto

�Árvore Geradora Mínima
�Caminho mais Curto
�Matching ou emparelhamento
�Coloração
�Roteamento de Veículos
�Localização de Facilidades
Problemas Clássicos
� Definição: dado um grafo G(V,E) conexo, 
não direcionado e associada a cada aresta 
de G uma distância (custo, tempo, etc.) 
não negativa.
� Uma árvore geradora de G é um subgrafo
gerador T de G tal que T é gerador e é uma 
árvore.
ÁRVORE GERADORA MÍNIMA
� O problema consiste em determinar a árvore geradora de G de custo 
mínimo, também chamada de árvore geradora mínima do grafo G.
� APLICAÇÕES:
� Projeto de Redes de Transmissão de energia
� Projeto de Redes de Computadores
� Projeto de rodovias, ferrovias
� Projeto de Redes de Telecomunicações (telefonia, TV a cabo, fibra 
ótica, etc.)
ÁRVORE GERADORA MÍNIMA
FUNDAMENTAÇÃO TEÓRICA
� Um grafo com n vértices requer somente n-1 arestas para fornecer um 
caminho que conecte todos os vértices.
� As n-1 arestas devem formar uma árvore geradora. O problema então é 
encontrar a árvore geradora com o menor comprimento total.
� O problema parte do princípio que existem apenas os vértices do grafo, 
e considera todas as ligações como “arestas potenciais”.
ÁRVORE GERADORA MÍNIMA
NOTA: O número de árvores geradoras em um grafo completo não-orientado é igual a nn-2.
Kruskal (1956)
Prim (1957)
Borüvka (1926)
A árvore Geradora Mínima atende as condições de uma
estrutura denominada Matróide*. Assim, pode ser solucionada
de forma exata através de procedimentos gulosos. Os
seguintes algoritmos são clássicos na literatura:
* Ver definição nos livros: 
• Campello, R. E.; Maculan, N. - Algoritmos e Heurísticas: Desenvolvimento e Avaliação de Performance, editora: Eduff, 1994.
• Korte, B.; Vygen, J. - Combinatorial Optimization: Theory and Algorithms, Springer, 2008 .
ÁRVORE GERADORA MÍNIMA
PRINCIPAIS ALGORITMOS:
� Algoritmo de Kruskal (publicado em 1956)
� Complexidade: O(E log V)
Cada iteração começa com uma floresta geradora F do grafo.
No início da primeira iteração, cada componente de F tem apenas um 
vértice.
Cada iteração consiste no seguinte:
1. se existe aresta externa a F 
1.1. então seja a uma aresta externa de custo mínimo 
1.2. comece nova iteração com F+a no papel de F 
2. senão pare
Se G for conexo, o algoritmo produz uma AGM de G. Caso contrário, o 
algoritmo produz uma AGM de uma das componentes de G.
Algoritmo de Kruskal
Ler G=(V,E) e D=[dij] a matriz distância de G.
Ordene as arestas de G em ordem crescente das distâncias dij no 
vetor A = [ai], i=1,2,...,m
T a1
i2
Enquanto |T| < n Tome ai  A e Faça
Início
Se T  ai é um grafo acíclico então
Início
TT  ai
ii+1
Fim
Caso Contrário
ii+1
Fim
Escrever T {arestas da árvore geradora mínima}
Lembrando:
T  árvore geradora
n  número de vértices
2
1
3 5
4
6
1
2
3
2
3
2
-31
3
1. (4-5) = -3
2. (1-2) = 1
3. (2-3) = 1
4. (2-4) = 2
5. (3-5) = 2
6. (5-6) = 2
7. (2-5) = 3
8. (4-6) = 3
Exemplo Algoritmo Kruskal
Exemplo Algoritmo Kruskal
2
1
3 5
4
6
1
2
3
2
3
2
-31
3
1. (4-5) = -3
2. (1-2) = 1
3. (2-3) = 1
4. (2-4) = 2
5. (3-5) = 2
6. (5-6) = 2
7. (2-5) = 3
8. (4-6) = 3
T = { 4,5} N 
Exemplo Algoritmo Kruskal
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
1. (4-5) = -3
2. (1-2) = 1
3. (2-3) = 1
4. (2-4) = 2
5. (3-5) = 2
6. (5-6) = 2
7. (2-5) = 3
8. (4-6) = 3
T = { 4,5,1,2} N 
Exemplo Algoritmo Kruskal
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
1. (4-5) = -3
2. (1-2) = 1
3. (2-3) = 1
4. (2-4) = 2
5. (3-5) = 2
6. (5-6) = 2
7. (2-5) = 3
8. (4-6) = 3
T = { 4,5,1,2,3} N 
Exemplo Algoritmo Kruskal
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
1. (4-5) = -3
2. (1-2) = 1
3. (2-3) = 1
4. (2-4) = 2
5. (3-5) = 2
6. (5-6) = 2
7. (2-5) = 3
8. (4-6) = 3
T = { 4,5,1,2,3} N 
Exemplo Algoritmo Kruskal
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
1. (4-5) = -3
2. (1-2) = 1
3. (2-3) = 1
4. (2-4) = 2
5. (3-5) = 2
6. (5-6) = 2
7. (2-5) = 3
8. (4-6) = 3
Ciclo (2-4-5-3-4) T = { 4,5,1,2,3} N 
Exemplo Algoritmo Kruskal
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
1. (4-5) = -3
2. (1-2) = 1
3. (2-3) = 1
4. (2-4) = 2
5. (3-5) = 2
6. (5-6) = 2
7. (2-5) = 3
8. (4-6) = 3
Ciclo (2-4-5-3-4)
Fim
T = { 4,5,1,2,3,6} = N  Fim 
PRINCIPAIS ALGORITMOS:
� Algoritmo de Prim (publicado em 1961)
� Complexidade: O(E + V log V)
No início de cada iteração do algoritmo de Prim temos uma árvore T.
No início da primeira iteração, T consiste em um único vértice.
Cada iteração consiste no seguinte:
1. se a franja de T não é vazia
1.1 então seja e uma aresta de custo mínimo na franja
1.2 comece nova iteração com T+e no papel de T
2. senão pare.
Se G for conexo, o algoritmo produz uma AGM de G. Caso contrário, o algoritmo produz 
uma AGM de uma das componentes de G. 
A franja de uma subárvore não-geradora T de G é o conjunto de todas as arestas de G que têm uma ponta em T e outra ponta fora. 
Se denotarmos por X o conjunto dos vértices de T e por Y o conjunto dos vértices fora de X, podemos dizer que a franja é o conjunto 
das arestas que pertencem ao corte (X,Y). 
Algoritmo de Prim
Ler G=(V,E) e D=[dij] a matriz distância de G. 
Escolha qualquer vértice iV
T {i}
QV \{i}
Enquanto T  V Faça
Início
Encontrar a menor aresta (j,k) E tal que jT, kQ
T  T  {k}
QQ \{k}
TMin  TMin  (j,k)
Fim
Escrever TMin {o conjunto das arestas da árvore geradora mínima}
Exemplo do Algoritmo Prim
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
Exemplo do Algoritmo Prim
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
T = { 1,2} N 
Exemplo do Algoritmo Prim
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
T = { 1,2,3} N 
Exemplo do Algoritmo Prim
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
T = { 1,2,3,5} N 
Exemplo do Algoritmo Prim
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
T = { 1,2,3,5,4} N 
Exemplo do Algoritmo Prim
2
1
3 5
4
6
1
2 
3 
2 
3 
2 
-3 1 
3 
T = { 1,2,3,5,4,6} = N  Fim 
Exemplo do Algoritmo Prim
2
1
3 5
4
6
1
2 
2 
-3 1 
EXEMPLO DE APLICAÇÃO 1:
O parque natural Seervada tem 7 postos de guarda que precisam ser 
interligados por linha telefônica. Os postos são representados pelos 
vértices no grafo a seguir, enquanto as arestas (rotuladas com seus 
comprimentos) são potenciais ligações para o projeto de rede telefônica.
O
C
B
D
A
E
T
2
4
7
5
4
2
1 3
5
1
7
4
EXEMPLO: Parque natural Seervada
Arbitrariamente, selecione o vértice O para iniciar. O vértice 
mais próximo de O não conectado é A. Conecte A.
CUSTO = 2
O
C
B
D
A
E
T
2
4
7
5
4
2
1 3
5
1
7
4
EXEMPLO: Parque natural Seervada
O vértice não conectado mais próximo dos nós O e A não 
conectado é o vértice B. Conecte B para A.
CUSTO = 4
O
C
B
D
A
E
T
2
4
7
5
4
2
1 3
5
1
7
4
EXEMPLO: Parque natural Seervada
O vértice não conectado mais próximo dos nós O, A e B 
não conectado é o vértice C. Conecte C para B.
CUSTO = 5
OC
B
D
A
E
T
2
4
7
5
4
2
1 3
5
1
7
4
EXEMPLO: Parque natural Seervada
O vértice não conectado mais próximo dos nós O, A, B e 
C não conectado é o vértice E. Conecte E para B.
CUSTO = 8
O
C
B
D
A
E
T
2
4
7
5
4
2
1 3
5
1
7
4
EXEMPLO: Parque natural Seervada
O vértice não conectado mais próximo dos nós O, A, B, C 
e E não conectado é o vértice D. Conecte D para E.
O
C
B
D
A
E
T
2
4
7
5
4
2
1 3
5
1
7
4
CUSTO = 9
EXEMPLO: Parque natural Seervada
O vértice não conectado mais próximo dos nós O, A, B, C, E 
e D não conectado é o vértice T. Conecte T para D.
O
C
B
D
A
E
T
2
4
7
5
4
2
1 3
5
1
7
4
CUSTO = 14
EXEMPLO: Parque natural Seervada
A solução final possui uma distância de 14 milhas. 
O
C
B
D
A
E
T
2
2
1 3
5
1
CUSTO = 14
EXEMPLO DE APLICAÇÃO 2: CLUSTERING – Classificação de espécies biológicas 
(“taxinomia”). [Também organizando materiais em bibliotecas, etc.]
� Definição: Dado um grafo G(V,A) conexo não direcionado com 
dois vértices especiais denominados O (origem) e D (destino), e 
associada a cada aresta de G uma distância (custo, tempo, etc.) 
não negativa. O problema consiste na minimização do custo de 
travessia do grafo entre dois vértices (O e D), custo este dado 
pela soma dos pesos de cada aresta percorrida.
� Aplicações:
� Dado um mapa rodoviário, determinar a rota mais curta de uma cidade a 
outra.
� Minimizar o custo (ou tempo) total de uma sequência de atividades.
CAMINHO MAIS CURTO (Shortest Path)
FUNDAMENTAÇÃO TEÓRICA
� Condição de existência: caminho de i a j contendo um 
circuito w: k
j
i
w
Comprimento do caminho = 
comprimento (i  k) +
comprimento (w) +
comprimento (k  j)
Qual é o comprimento do caminho mais curto de i a j se o 
comprimento do circuito w é negativo?
Material de: Celso C. Ribeiro e Caroline T. Rocha
CAMINHO MAIS CURTO (Shortest Path)
� Condição de existência:
�Não há circuitos de comprimento negativo.
A solução ótima (caminho mais curto) sempre será um caminho 
elementar (sem circuito).
 VARIAÇÕES DO PROBLEMA: 
De um vértice a qualquer outro vértice do grafo
De um vértice para todos os demais vértices do grafo
Entre todos os pares de vértices do grafo 
Exemplo: Construção de uma estrada entre duas cidades A e K. O grafo 
abaixo representa os diversos trechos possíveis e o custo de construção de 
cada um. Determinar o trajeto ótimo cujo custo de construção seja mínimo 
(corresponde a achar o caminho mais curto de A a K em relação a estes 
custos).
A
B
C
D
F
E
G J
I
H
K
8
7
5
6 4
2 4
5
4
4
2
244
5
2 4 4
Solução: A – D – G – I – K
custo = 7 + 2 + 2 + 5 = 16
� Férias na Romênia [Russell, Stuart]
� Localização (estado) atual :
� Arad
� Objetivo :
� Chegar a Bucareste
� Restrição :
� Vôo no dia seguinte 
partindo de Bucareste
� Formulação do problema :
� Estados : as várias cidades
� Ações : dirigir entre as cidades
� Busca da solução :
� Gerar seqüências de cidades. Ex. : (Arad, Sibiu, Fagaras, Bucareste)
MCC - UERN/UFERSA
�Férias na Romênia
89
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
120
87
Estratégias de Busca
� Busca pela melhor escolha
� Idéia Básica: selecionar para expansão o melhor nó, segundo 
uma função de avaliação (n) que estima quão “desejável” é 
tal nó. Assim, a idéia é:
� Estimar a prioridade de cada nó
� Expandir o nó prioritário ainda não visitado
� Implementação:
� Utilizar uma fila de prioridades mantendo a borda ordenada 
pelos valores ascendentes (maximização) de (n)
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
176
138
146
97
99
80
151
140
111
70
75
118
75
71
87
Busca Gulosa – f(n) como Rotas de menor peso
09/04/
2019
MCC - UERN/UFERSA
Zerind 75 Sibiu 140 Timisoara 118
120
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
09/04/
2019
MCC - UERN/UFERSA
Oradea 71
120
Custo = 75
Busca Gulosa – f(n) como Rotas de menor peso
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
09/04/
2019
MCC - UERN/UFERSA
Sibiu 151
120
Custo = 146
Busca Gulosa – f(n) como Rotas de menor peso
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
09/04/
2019
MCC - UERN/UFERSA
Fagaras 99 R. Vilcea 80
120
Custo = 297
Busca Gulosa – f(n) como Rotas de menor peso
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
09/04/
2019
MCC - UERN/UFERSA
Pitest 97 Craiova 146
120
Custo = 377
Busca Gulosa – f(n) como Rotas de menor peso
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
09/04/
2019
MCC - UERN/UFERSA
Bucareste 101
120
Custo = 474
Busca Gulosa – f(n) como Rotas de menor peso
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
09/04/
2019
MCC - UERN/UFERSA 120
Custo = 575
Busca Gulosa – f(n) como Rotas de menor peso
86
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
9885
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
Busca Gulosa – possível problema
Não é CompletaNovo objetivo : ir de Iasi à Fagaras
Caminho infinito !
120
Oradea
Zerind
Arad
Timisoara Lugoj
Mehadia
Dobreta
CraiovaPitest
Rimnieu Vilcea
Fagaras
Sibiu
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Iasi
Neamt
226
199
151
161
80
77
242
176
160
241
100
193
380
366
329
244
374
253
Bucareste
234
Busca Gulosa – f(n) como distância em linha reta com menor peso
Estratégias de Busca
� Casos Especiais de Busca pela Melhor Escolha :
� Busca Gulosa : tenta expandir o nó mais próximo ao objetivo, na
suposição de que tal procedimento levará a uma solução mais
rápida. Isto é feito utilizando a função de avaliação (n)=h(n)
� Exemplo de aplicação :
Férias na Romênia (Heurística hDLR)
Cidade Prox. meta Cidade Prox. meta
Arad 366 Mehadia 241
Bucareste 0 Neamt 234
Craiova 160 Oradea 380
Dobreta 242 Pitesti 100
Eforie 161 Riminicu Vilcea 193
Fagaras 176 Sibiu 253
Giurgiu 77 Timisoara 329
Hirsova 151 Urziceni 80
Iasi 226 Vaslui 199
Lugoj 244 Zerind 374
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
Busca Gulosa – f(n) como distância em linha reta com menor peso
09/04/
2019
MCC - UERN/UFERSA
Sibiu 253 Timisoara 329 Zerind 374
120
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87Custo = 140
09/04/
2019
MCC - UERN/UFERSA
Sibiu Fagaras 176 Oradea 380 Rimnieu Vilcea 193
120
Busca Gulosa – f(n) como distância em linha reta com menor peso
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87Custo = 239
09/04/
2019
MCC - UERN/UFERSA
Sibiu Fagaras Sibiu 253 Bucareste 0
120
Busca Gulosa – f(n) como distância em linha reta com menor peso
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
16/04/
2019
MCC - UERN/UFERSA
Sibiu Fagaras Bucareste Não é Ótima
120
Busca Gulosa – f(n) como distância em linha reta com menor peso
Custo = 450
Estratégias de Busca
Estratégias mais elaboradas
Casos Especiais de Busca pela Melhor Escolha:
� Busca A*: avalia os nós do grafo combinando uma heurística g(n) 
que considera o custo para alcançar cada nó, e h(n), que considera 
o custo de ir do nó inicial ao nó objetivo, ou seja (n)=g(n)+h(n)
� (n) pode ser vista com a função de custo estimado da solução de 
custo mais baixo passando por n
� O algoritmo A* é a forma mais conhecida de busca pela melhor 
escolha
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87Custo= 0+366
Busca Gulosa – Exemplo de Aplicação
09/04/
2019
MCC - UERN/UFERSA
Custos : Zerind = 75+374 / Sibiu = 140+253 / Timisoara = 118+329
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87Custo= 140+253
Busca Gulosa – Exemplo de Aplicação
09/04/
2019
MCC - UERN/UFERSA
Custos : Arad = 140+366 / Fagaras = 99+176 / Oradea = 151+380 / R. Vilcea = 80+193
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87Custo = 220+193
Busca Gulosa – Exemplo de Aplicação
09/04/
2019
MCC - UERN/UFERSA
Custos : Craivoa = 146+160 / Pitest = 97+100 / Sibiu = 80+253
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87Custo = 317+100
Busca Gulosa – Exemplo de Aplicação
09/04/
2019
MCC - UERN/UFERSA
Custos : Bucareste = 101+0 / Craiova = 138+160 / R. Vilcea = 97+193
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Pitest
Rimnieu Vilcea
FagarasSibiu
Bucareste
Giurgiu
Eforie
HisorvaUrziceni
Vaslui
Lasi
Neamt
92
142
98
86
85
90
101
211
138
146
97
99
80
151
140
111
70
75
118
75
71
87
Custo = 418+0
Busca Gulosa – Exemplo de Aplicação
09/04/
2019
MCC - UERN/UFERSA