DR. JOSÉ MARTÍNEZ CARRANZA

CIENCIAS COMPUTACIONALESINAOE

Análisis y Diseño de AlgoritmosGrafos

2

Grafos Dirigidos2

3

Grafos Dirigidos

El camino de un grafo dirigido es una secuencia de vértices v1,v2,...,vn tal que: v1 -> v2, v3 -> v3,…, vn-1 -> vn son arcos.

La longitud de un camino es el número de arcos en sesecamión, en este caso, n-1.

Un vértice sencillo, v, por sí mismo denota un camión de longitud cero de v a v.

3

4

Representación4

55

Cámino más corto entre dos nodos

Algoritmos: Búsqueda en profundidad (Recursivo) Expansión por niveles (uso de colas) Programación Dinámica

5

66

Cámino más corto entre dos nodos6

13/11/2018

Algoritmo Dijkstra

13/11/2018

Algoritmo Dijkstra

13/11/2018

Algoritmo Floyd