Dijkstra

Grafos
Grafos Ponderados y
Caminos de Longitud Mínima

Escuela de Ingeniería de Sistemas y
Computación
Universidad del Valle

1

Grafos Ponderados
Son aquellos grafos en los que se asignaun número a
cada una de las aristas.
Boston
191
Chicago

Nueva York

957

San Francisco

Denver

Atlanta

349
Los Ángeles
Miami
2

Grafos Ponderados
Se utilizan pararepresentar:
Redes Informáticas y costo de transmisión de datos.
Redes Informáticas y tiempo de transmisión de datos.
Tiempo de respuesta o distancia entre computadores.
Distancia entre ciudades.
Costo detransporte entre ciudades.
3

Grafo Ponderado con Tiempos
Boston
0:50
Chicago

Nueva York

San Francisco
Denver
1:15

Atlanta

Los Ángeles
Miami

4

Grafo Ponderado con CostosBoston
$39
Chicago

Nueva York

San Francisco
Denver
$39

Atlanta

Los Ángeles
Miami

5

Longitud de un Camino
En un grafo ponderado, la longitud de un camino es la
suma de lospesos de las aristas que componen el
camino.
Se debe diferenciar el concepto de longitud en grafos
ponderados y sin ponderar.
Existen diversos problemas relacionados con grafos
ponderados. Uno deellos es conocer:
¿Cuál es el camino más corto?, esto es el camino
de longitud mínima entre dos vértices dados.
6

Algoritmo para Calcular
Caminos de Longitud Mínima
Existen diversos algoritmospara hallar caminos de
longitud mínima entre dos vértices de un grafo
ponderado.
Uno de éstos es el Algoritmo de Dijkstra.
El algoritmo de Dijkstra determina el camino y la longitud
mas cortaentre dos vértices de un grafo ponderado
simple, conexo y no dirigido.

7

Algoritmo de Dijkstra
ALGORITMO DE DIJKSTRA
proc Dijkstra(G: grafo ponderado simple y conexo, con pesos positivos,
a:vértice inicial del camino mínimo que se desea hallar,
z: vértice final del camino mínimo que se desea hallar)
{G tiene vértices a=v0,v1,…,Vn=z y pesos w(vi,vj),
donde w(vi,vj)= si {vi,vj} no es...