Matematicas discretas. Actividad Didáctica 6 Problema del camino más corto

Actividad Didáctica 6

Problema del camino más corto

Introducción

El problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.

Algoritmo de Dijkstra: también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.

        Otro algoritmo que resuelve el problema es el algoritmo de Prim que encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

El software MaGraDa (Grafos para Matemática Discreta) es un programa de software libre, elaborado en el lenguaje JAVA y diseñada específicamente para trabajar con grafos.

MaGraDa trabaja con grafos tanto dirigidos como no dirigidos y ponderados como no ponderados. Según la filosofía de MaGraDa se puede trabajar con un número ilimitado de vértices, pero es conveniente sólo permitir trabajar con grafos de hasta un máximo de 50 vértices.

Este paquete es sencillo y cómodo de manejar, está basado en menús sobre pantalla.

Actividad:         con MaGraDa (http://www.dccia.ua.es/~jpenades/MaGraDa/MaGraDa.ZIP), que es software libre, encontrar el camino más corto del siguiente grafo:

[pic 1]

Para ello utilizar los algoritmos de Dijkstra y de Prim. En ambos casos iniciar en el vértice A y H, comparando los resultados obtenidos en cada caso. ¿Por qué la diferencia de pesos en los grafos resultantes?

...