algoritmo mas cortos

TEORÍA DE GRAFOS:
ALGORITMOS
FUNDAMENTALES
BIANKA BARRIOS S.

2

s

b
1

3

a

2

d

1

2

20

55

t
c

2

45

3

4
3

10

5

25

40

30

25
504

15

Algoritmos de caminos más cortos

3

CAMINOS MAS CORTOS
• Frecuentemente, se desea conocer en una red
– Cual es el camino mas corto
• Entre un par de vértices

– En este caso

•Si importa cuantos caminos existen
• Si ya conozco un camino, pero encuentro uno mejor, sustituir

• Se aplica el algoritmo de Dijkstra
– Es un algoritmo avido, ya que:

• Resuelve el problemaen sucesivos pasos
• En cada paso
– Selecciona la solución mas optima

Algoritmos de caminos más cortos
• El problema de los caminos más cortos desde un vértice.
– Algoritmo de Dijkstra.

•El problema de los caminos más cortos entre todos los
pares de vértices.
– Algoritmo de Floyd.

• Árbol de Expansión Mínima
– Kruskal
– Prim

Grafos con pesos
• Cada arista lleva asociado unvalor numérico no negativo, w(e),
que representar un costo que varía linealmente a lo largo de la
arista (distancia, tiempo).
• El costo de un camino es la suma de los costos de las aristas
delcamino.
COR



Ejemplo: grafo que representa

las rutas entre ciudades de una
aerolínea. El peso de las aristas
es el tiempo de vuelo.

SAN

2

1.1

1

1.5

MAD

1
1.2
1.2

1VAL

2

1.2
1.3
SEV
MAL

BIL

1.5

0.9
BAR

Algoritmo de Dijkstra
•
•
•
•

•

La idea principal es realizar una búsqueda a lo ancho “ponderada”
empezando por el vérticeinicial f.
De manera iterativa se construye un conjunto de vértices
seleccionados S que se toman del conjunto de vértices candidatos C
según el menor peso (distancia) desde f.
El algoritmo terminacuando no hay más vértices de G fuera del
conjunto formado.
El paradigma usado corresponde al método voraz, en el que se trata
de optimizar una función sobre una colección de objetos (menor
peso)....