la sexualidad
Páginas: 3 (610 palabras)
Publicado: 22 de enero de 2014
Algoritmos para caminos más cortos
comp-420
Algoritmo de Moore (Bellman-Ford)
•
Dado una gráfica dirigida con pesos en sus aristas con fuente s y función de peso
w: E→R, el algoritmo deMoore regresa un valor booleano indicando si hay o no un
cíclo negativo alcanzable desde la fuente.
•
Si existe un cíclo negativo, el algoritmo declara que no existe una solución.
•
Si noexiste, el algoritmo produce el camino más corto.
•
El algoritmo usa relajación, reduciendo progresivamente el estimado d[v] en el peso
del camino más corto a partir de s hasta todos los vérticesv∈V hasta que alcanza
el peso del camino más corto δ(s,v).
Algoritmo de Moore (Bellman-Ford)
Bellman-Ford (G, w, s)
1
2
3
4
5
6
7
8
Initialize-Single-Source(G, s)
for i ← 1 to |V[G]| − 1
do for each edge (u, v) ∈ E[G]
do Relax(u, v, w)
for each edge (u, v) ∈ E[G]
do if d[v] > d[u] + w(u, v)
then return False
return True
Initialize-Single-Source (G, s)
1 for eachvertex v ∈ V [G]
2
do d[v] ← ∞
3
π[v] ← NIL
4 d[s] ← 0
Relax (u, v, w)
1 if d[v] > d[u] + w(u, v)
2
then d[v] ← d[u] + w(u, v)
3
π[v] ← u
Algoritmo de Moore (Bellman-Ford)
t
5
xt
5
x
6
-2
!
2
-2
4
6
s
8
0
6
-3
2
7
7
-4
s
7
t
!
9
y
-2
!
z
6
s
2
7
t
5
x
6
-2
4
6
s
27
7
y
• O(VE)
y
7
7
!
9
-4
2
z
2
9
z
9
-4
7
!
t
x
2
z
5
-2
4
6
7
-4
y
-3
8
0
!
2
7
-3
8
0
8
0x
5
-3
-3
8
0
2
7
7
y
9
-4
7
-2
z
Algoritmo de Dijkstra
•
Edsger W. Dijkstra (1930-2002)
•
Pionero de la ciencia e industria de la computación.
•Matemático y físico teórico con PhD en Ciencias de la Computación.
•
Turing Award en 1972.
•
Fue de los primeros en opinar que la lógica matemática matemática es
indispensables para...
comp-420
Algoritmo de Moore (Bellman-Ford)
•
Dado una gráfica dirigida con pesos en sus aristas con fuente s y función de peso
w: E→R, el algoritmo deMoore regresa un valor booleano indicando si hay o no un
cíclo negativo alcanzable desde la fuente.
•
Si existe un cíclo negativo, el algoritmo declara que no existe una solución.
•
Si noexiste, el algoritmo produce el camino más corto.
•
El algoritmo usa relajación, reduciendo progresivamente el estimado d[v] en el peso
del camino más corto a partir de s hasta todos los vérticesv∈V hasta que alcanza
el peso del camino más corto δ(s,v).
Algoritmo de Moore (Bellman-Ford)
Bellman-Ford (G, w, s)
1
2
3
4
5
6
7
8
Initialize-Single-Source(G, s)
for i ← 1 to |V[G]| − 1
do for each edge (u, v) ∈ E[G]
do Relax(u, v, w)
for each edge (u, v) ∈ E[G]
do if d[v] > d[u] + w(u, v)
then return False
return True
Initialize-Single-Source (G, s)
1 for eachvertex v ∈ V [G]
2
do d[v] ← ∞
3
π[v] ← NIL
4 d[s] ← 0
Relax (u, v, w)
1 if d[v] > d[u] + w(u, v)
2
then d[v] ← d[u] + w(u, v)
3
π[v] ← u
Algoritmo de Moore (Bellman-Ford)
t
5
xt
5
x
6
-2
!
2
-2
4
6
s
8
0
6
-3
2
7
7
-4
s
7
t
!
9
y
-2
!
z
6
s
2
7
t
5
x
6
-2
4
6
s
27
7
y
• O(VE)
y
7
7
!
9
-4
2
z
2
9
z
9
-4
7
!
t
x
2
z
5
-2
4
6
7
-4
y
-3
8
0
!
2
7
-3
8
0
8
0x
5
-3
-3
8
0
2
7
7
y
9
-4
7
-2
z
Algoritmo de Dijkstra
•
Edsger W. Dijkstra (1930-2002)
•
Pionero de la ciencia e industria de la computación.
•Matemático y físico teórico con PhD en Ciencias de la Computación.
•
Turing Award en 1972.
•
Fue de los primeros en opinar que la lógica matemática matemática es
indispensables para...
Leer documento completo
Regístrate para leer el documento completo.