Pascal/Turbo Pascal - Grafo no dirijido (Lista adyacencia)

Muy buenas tardes, amigos!
Necesito su valiosa ayuda para realizar un programa que pueda crear una estructura de grafo. Luego, el programa debe leer 2 ciudades y calcular la distancia entre éstas. Lógicamente existen muchas rutas (o caminos), pero se debe seleccionar la de menor distancia (al parecer se trata del clásico problema del camino mínimo [Dijkstra] ).
Las aristas (o arcos) tienen peso, en consecuencia estamos hablando de un grafo ponderado, pero no dirigido.
No tengo mucha experiencia con este tipo de estructura, por lo que agradecería me indicaran cómo debo definir el tipo (el TYPE) y también el procedimiento de búsqueda usando el algortimo de la ruta más corta.

****************** MUCHAS GRACIAS A TODOS!!!!!!! ***********************

Post data: El trabajo es para el martes 27/06/2007 (es deci, el martes de la semana que viene!!!!!!!)

Hola.

Creo que puedo ayudarte. Mándame una descripción un poco más detallada al mail y hablamos. Lo que si te puedo decir de antemano es que la mejor forma de abordar este problema es mediante una función recursiva.

Saludos.

Muchas gracias, Klaytor!!
Bueno, ya conseguí por un Internet un Código muy útil para realizar la estructura como tal, así como varias funciones que devuelven: el número de nodo, la etiqueta del nodo y de la arista, etc.

Ahora lo que me resta es hacer un proc. (o ensamblar las que ya tengo) para determinar la ruta o camino más corto entre 2 nodos (ciudades) diferentes.

Te agradezco mucho si me puedes ayudar con un algoritmo para esto.

Chao!!!!

Hola.

Dices que el programa lee dos ciudades y tiene que devolver la ruta mínima entre ellas pero, me imagino que también tendrá que leer las posibles rutas que hay entre ambas ciudades, no??

Si me pasases el código que tienes podría echarle un vistazo. De todas formas yo haría algo como lo siguiente para calcular la distancia mínima.

Supongo que cada nodo (ciudad) tiene N punteros, cada uno señalando a una posible ruta (de las N posibles) y cada uno con su correspondiente ponderación, es decir, te quedaría una estructura para cada nodo(ciudad) tal que así:

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ruta0: variable_puntero;
coste0: integer; //ponderación de la ruta
ciudad0:integer; //ciudad a la que vamos si tomamos la ruta0
ciudad_nodo: T_XYZ; //ciudad que representa este nodo
ruta1: variable_puntero;
coste1: integer;
ciudad1:integer;
ciudad_nodo: T_XYZ;
...
...
rutaN:variable_puntero;
costeN:integer;
ciudadN:integer;
ciudad_nodo: T_XYZ;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

La funcion recursiva que calcularía la ruta mínima podría ser la siguiente:

FUNCTION Calcula_Ruta_Minima(ciudad_origen: T_CIUDAD; ciudad_destino: T_CIUDAD; coste: INTEGER):INTEGER;
BEGIN

VAR
___lista_costes: ARRAY[1 .. N] OF INTEGER;

IF (puntero^.ruta0^.ciudad <> ciudad_destino) THEN Calcula_Ruta_Minima(puntero^.ruta0, ciudad_destino, coste + puntero^.coste0);
IF (puntero^.ruta1^.ciudad <> ciudad_destino) THEN Calcula_Ruta_Minima(puntero^.ruta1, ciudad_destino, coste + puntero^.coste1);
...
...
IF (puntero^.rutaN^.ciudad <> ciudad_destino) THEN Calcula_Ruta_Minima(puntero^.rutaN, ciudad_destino, coste + puntero^.costeN);

//---------------------------------------------------------------------------------------------------------------
IF (puntero^.ruta0^.ciudad = ciudad_destino) THEN lista_costes[1]:=coste;
IF (puntero^.ruta1^.ciudad = ciudad_destino) THEN lista_costes[2]:=coste;
...
...
IF (puntero^.rutaN^.ciudad = ciudad_destino) THEN lista_costes[N]:=coste;

Calcula_Ruta_Minima:=MINIMO_VALOR_ARRAY_DE_COSTES(lista_costes);
END;

//La funcion devuelve el coste de la ruta mínima
//Puntero sería el comienzo de la ruta, es decir, la ciudad_origen (en la primera ejecución)

Espero que te sirva de algo.

Saludos.