Sfswerewr

Solo disponible en BuenasTareas
  • Páginas : 8 (1934 palabras )
  • Descarga(s) : 0
  • Publicado : 3 de febrero de 2012
Leer documento completo
Vista previa del texto
Introducción
Un grafo es una estructura de datos que se utiliza entre otras situaciones para representar conexiones entre ciudades y sus pesos.
Las conexiones entre las distintas ciudades son bidireccionales, es decir si hay dos ciudades A y B (vértices) y existe una conexión entre ellas, se entiende que hay posibilidad de viajar de A a B y de B a A.
A continuación se muestra un posibleejemplo de 8 ciudades (llamadas de A..H) y las posibles conexiones que existen entre ellas.

En el grafo anterior tenemos las siguientes relaciones entre los vértices:
De | A | Peso |
A | B | 3 |
| C | 5 |
| D | 2 |
| H | 10 |
| De | A | Peso |
B | A | 3 |
| C | 5 |
| D | 6 |
| E | 4 |
| G | 6 |
| H | 6 |
| De | A | Peso |
C | A | 5 |
| B | 5 |
| E | 1 || G | 9 |
| F | 7 |
|
De | A | Peso |
D | A | 2 |
| B | 8 |
| E | 12 |
| H | 14 |
| De | A | Peso |
E | B | 4 |
| C | 1 |
| D | 12 |
| G | 15 |
| De | A | Peso |
F | C | 7 |
| H | 9 |
| | |
| | |
|
De | A | Peso |
G | B | 6 |
| C | 9 |
| E | 15 |
| H | 3 |
| De | A | Peso |
H | A | 10 |
| B | 6 |
| D | 14 |
| F | 9|
| G | 3 |
| |

El peso asociado en los vértices puede representar la distancia entre dos puntos, o bien tiempo de viaje o costo de un tiquete. Los vértices pueden almacenar más de un valor.

El proyecto – Parte 1
La idea es crear un grafo que represente las interconexiones existentes en un total de 8 ciudades, cuyos nombres se encuentran alojados en un archivo de texto llamadoCIUDADES.TXT
Cada vértice almacenará dos variables de peso importante: tiempo y costo que representarán el tiempo en minutos necesarios para trasladarse de un punto a otro y el costo que representa este traslado y serán cargados desde un archivo de texto llamado CONEXIONES.TXT, en el cual sólo aparecerá una de las conexiones y deberá representarse dicha conexión en ambas direcciones.
Al final de lacarga de los archivos no debe quedar ningún vértice (nodo) sin conectar.
Es decir si el archivo tiene una entrada A,B,12,8 deberá interpretar que tanto para ir de A a B como de B a A hay un peso en tiempo de 12 unidades y un tiempo en costo de 8 unidades.
La representación de esta estructura se realiza sobre una lista de listas donde la lista base contendrá la información de las ciudades y lassub listas de cada una las conexiones hacia otras ciudades.
Considere la posibilidad de plantear su solución como listas de adyacencia o una matriz de adyacencia.
EL problema que nos interesa resolver con una estructura de grafos es hallar la ruta más corta entre dos puntos cualesquiera A y B, para lo cual se hará uso del algoritmo llamado algoritmo de Dijkstra que fue analizado en clase.
Laidea es que el usuario pueda ingresar un punto de referencia A y a partir de él se calcule el algoritmo de Dijkstra para hallar la ruta más corta desde ese punto a cualquiera otro del grafo.
El usuario puede seleccionar el tipo de factor a tomar en consideración (tiempo o costo) y por medio de la ejecución del algoritmo se pueda determinar cuál es la ruta más corta para el grafo que representa ladistribución de ciudades.
Algoritmo de Dijkstra
El 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. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea en este algoritmo consiste en ir explorandotodos 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.

El algoritmo
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las...
tracking img