Computacionii

Solo disponible en BuenasTareas
  • Páginas : 4 (760 palabras )
  • Descarga(s) : 0
  • Publicado : 11 de enero de 2012
Leer documento completo
Vista previa del texto
program dijkstra(input, output);
(*
Implementacion del algoritmo de Dijkstra para
encontrar un camino mas corto entre dos vertices
en un grafo pesado.

Entrada: un grafo pesado dado por listade aristas,
el numero de vertices, n, y los vertices a unir, s y t.
Los vertices son todos los enteros positivos
entre 1 y n. Si alguno no aparece en ninguna
arista, es un vertice aislado.
Lospesos de cada arista son enteros positivos.

Salida: la longitud de un camino mas corto, y el
camino que lo realiza como lista de vertices. Si
los vertices no se pueden conectar, se imprime unmensaje.
*)

const
MAXN = 20; (* maximo numero de vertices *)
MAXM = 100; (* maximo numero de aristas *)

type
costo = integer; (* podria ser real *)
arreglodevertices = array[1..MAXN] of integer;tipoarista = record
i, j: integer; (* los extremos *)
w: costo (* el costo *)
end;
arreglodearistas = array[1..MAXM] of tipoarista;
matrizNN = array[1..MAXN,1..MAXN] of costo;

var
ngrafo,mgrafo, s, t: integer;
infinito: costo;
padre: arreglodevertices;
dist: array[1..MAXN] of costo;
aristasgrafo: arreglodearistas;
costos: matrizNN;

function nuevaarista: boolean;
beginwriteln;
write(' Entrar la arista ', mgrafo:2);
writeln(' (fin = ): ');
write(' Entrar el primer vertice: ');
if (not eoln) then begin
nuevaarista := true;
with aristasgrafo[mgrafo] do begin
read(i);write(' Entrar el segundo vertice: ');
read(j);
write(' Entrar el costo (entero > 0): ');
readln(w)
end (* with *)
end (* if not eoln *)
else begin nuevaarista := false; readln end
end;procedure entrardatos;
begin
(* vertices *)
writeln;
write('Entrar el numero de vertices: ');
readln(ngrafo);
(* aristas *)
writeln;
writeln('Entrar las aristas:');
mgrafo := 1;
while(nuevaarista) do mgrafo := mgrafo + 1;
mgrafo := mgrafo - 1;
(* vertices a unir *)
writeln;
write('Entrar el vertice de partida: '); readln(s);
write('Entrar el vertice de llegada: '); readln(t)
end;...
tracking img