Algoritmo del camino mas Corto

Si exacto DEACHP eso es a lo que me refiero pero el metodo de Dikjistra no es que quiero el CPM (Critical Path Method) metodo de la ruta mas Corta es el que estoy programando ya que ese metodo tienen varios usos.
Si es que alguien me puede ayudar.

Saludos compañeros:

Aqui les mando un ejemplo de un poblema y el uso del algoritmo hecho a mano es sencillo pero lo que yo quiero es que aparte de darme las iteraciones al final me de el camino,en el ejemplo el camino seria 1-2-3-5 y el valor del camino es 7896
Cualquier Duda me la hacen llegar
En este problema lo que se busca es la ruta mas corta del punto 1 al punto 5

Donde dij :Distancia desde el punto i ap punto j.(Datos del problema)
Donde mi:Ruta mas Corta al punto i(Lo halla en cada iteracion)
m1=0
m2=m1+d12=1700
m3=min {m1+d13, m2+d23}=min {3968,3580}=3580
m4=min {m1+d14, m2+d24, m3+d34}=min {7622, 6352, 5880}=5880
m5=min {m1+d15, m2+d25, m3+d35, m4+d45}=min {10970, 9196, 7896, 8600}=7896

Retrocediendo
Como m5=7896 viene de m3+d35 entonces nos vamos a m3
Como m3=3580 viene de m2+d23 entonces nos vamos a m2
Como m2=1700 viene de m1+d12 entonces nos vamos a m1
Por lo tanto el camino mas corto es 1-2-3-5

En verdad lo que yo pienso hacer es crear y programa que tenga todos los algoritmos necesarios para Investigacion Operativa II:
Camino mas corto
Arbol de expansion Minima
Flujo Maximo
Proyectos CPM/PERT
Programacion Dinamica
Modelo de Colas
Y mas
que son los que mayormente se usan es esta materia
Por lo pronto tengo problemas con el primero Camino mas Corto ya estoy por terminar el segundo Arbol de......
agradeceria la ayuda
Gracias

sALUDOS AMIGOS ACA TENGO MI PROGRAMITA me pueden decir en que esta mal es que no encuentro el error me sale eror argumento pero no se porque voy a revisarlo pero si pueden darme una mano lo agradeceria.
CMC:
"Camino mas Corto"
{
{ "Arcos" "Usando el Editor de Matrices" }
}
{ 1 0 }
{ }
{ }
INFORM
IF
THEN
OBJ DROP
{0} 0 0  d m min n
« d SIZE OBJ DROP 'n' STO DROP

2 n FOR i
Ÿ 'min' STO
1 'i-1' EVAL FOR j
min
'm(j)+ d(j,i)' EVAL
MIN 'min' STO
NEXT
m min +
NEXT
m
»
END
»

Saludos a todos:
Gracias DEACHP por tu correcion sobre todo la tercera en dodne me olvide de guardar la nueva lista despues de concatenar.
Sin embargo la segunda correcion no es correcta el algoritmo completo es 'm(j)+d(j,i)' o en tu programa seria 'm(j)+d(i,j)' ya que has invertido la matriz.
Lo que pasa es que m(j ) simboliza el camino mas corto desde el punto 1 a el punto j por lo tanto tiene que sumarse a d(j,i) para hallar la distancia total es decir :
m(j ) = Distancia Minima desde el punto 1 hasta el punto j
d(j,i) =Distancia desde el punto j al punto i
El minimo de 'm(j)+d(j,i)'= Distancia minima desde el punto 1 hasta el punto i
Los datos del ejemplo que pusiste no eran los correctos,los datos son las distancias entre los diferentes puntos
d(1,2)=1700
d(1,3)=3968
d(1,4)=7622
d(1,5)=10970

d(2,3)=1880
d(2,4)=4652
d(2,5)=7496

d(3,4)=2300
d(3,5)=4316

d(4,5)=2720

En la matriz seria:
[[ 0. 1700. 3968. 7622. 10970.]
[ 0. 0. 1880. 4652. 7496.]
[ 0. 0. 0. 2300. 4316.]
[ 0. 0. 0. 0. 2720. ]]

metiendo esto en la matriz d el resultado es:
{ 0. 1700. 3580. 5880. 7896. }
Donde 7896 es el valor del camino mas corto desde 1 hasta el punto 5

Ahora ese problema ya esta solucionado pero aca la parte que necesito ayuda:
¿COMO SABER CUAL ES EL CAMINO ES DECIR POR QUE PUNTOS PASA PORQUE A SOLUCION COMPLETA ES:
Valor del Camino = 7896 (Listo)
Camino conformado por los puntos = 1 -2 -3 - 5 (Falta)

Asi se hace manualmente :
m1=0
m2=m1+d12=1700
m3=min {m1+d13, m2+d23}=min {3968,3580}=3580
m4=min {m1+d14, m2+d24, m3+d34}=min {7622, 6352, 5880}=5880
m5=min {m1+d15, m2+d25, m3+d35, m4+d45}=min {10970, 9196, 7896, 8600}=7896

Retrocediendo
m5
Como m5=7896 viene de m3+d35 entonces nos vamos a m3
Como m3=3580 viene de m2+d23 entonces nos vamos a m2
Como m2=1700 viene de m1+d12 entonces nos vamos a m1
Por lo tanto el camino mas corto es 1-2-3-5

Te dejo el codigo ya modificado para haber si me pueden ayudar a solucionar ese problema:
Gracias

«
"Camino mas Corto"
{
{ "Arcos" "Usando el Editor de Matrices" }
}
{ 1 0 }
{ }
{ }
INFORM
IF
THEN
OBJ DROP
{0} 0 0  d m min n
« d SIZE OBJ DROP 'n' STO DROP

2 n FOR i
Ÿ 'min' STO
1 'i-1' EVAL FOR j
min
'm(j)+ d(j,i)' EVAL
MIN 'min' STO
NEXT
m min + 'm' STO
NEXT
m
»
END
»

Saludos a todos lo miembros
hola DEACHP acabo de acabar mi programa para hallar el camino mas Corto y justo me di cuenta que tu mandaste tambien bueno recien voy a revisar lo que me mandaste para analisarlo y aprender mas sobre programacion ,seguro es muy bueno.
Mas bien dime que opinas de mi programa y en que se puede mejorar te lo agradeceria mucho
Aca te mando mi programa para que le des una revisada:
« "Camino mas Corto"
{{ "Arcos" "Usando el Editor de Matrices" }}
{ 1 0 }{ }
IF 'CMC.dat' VTYPE 5 ==
THEN CMC.dat
ELSE { }
END
INFORM
IF
THEN
DUP 'CMC.dat' STO
OBJ DROP
{0}{}{0} 0 0 0 0 0  d m ca c min mina n k x
« d SIZE OBJ DROP 'n' STO DROP
ca n + 'ca' STO
2 n FOR i
Ÿ 'min' STO
1 i 1 - FOR j
min
'm(j)+ d(j,i)' EVAL
MIN 'mina' STO
IF 'min‹mina'
THEN j 'k' STO
END
mina 'min' STO
NEXT
m min + 'm' STO
c k + 'c' STO
NEXT
n 'x' STO
DO
'c(x)' EVAL DUP 'x' STO
ca + 'ca' STO
UNTIL 'x==1'
END
CLLCD "Magnitud del Camino mas Corto: " m REVLIST HEAD + MSGBOX
"Camino mas Corto: " ca STR + MSGBOX
» END »

Ingresamos la matriz distancias:

[[ 0. 1700. 3968. 7622. 10970.]
[ 0. 0. 1880. 4652. 7496.]
[ 0. 0. 0. 2300. 4316.]
[ 0. 0. 0. 0. 2720.]]

y se ejecuta el programa 'CMC':
Magnitud del Camino mas Corto: 7896
Camino mas Corto: {1 2 3 5}

CesarMoriF Estudiante de Ingenieria Industrial Universidad Nacional Mayor de San Marcos

Mis saludos a todos
Muchas gracias por tu aporte Deachp voy a cambiar lo que me dijiste en mi programa tienes razon si lo pongo en RPN es mas rapido.
Ahora quisiera completar el programa para esto faltan dos puntos imoportantes:
1)Quiero hacer que me vote el procedimiento manual es decir lo siguiente:
m1=0
m2=m1+d12=1700
m3=min {m1+d13, m2+d23}=min {3968,3580}=3580
m4=min {m1+d14, m2+d24, m3+d34}=min {7622, 6352, 5880}=5880
m5=min {m1+d15, m2+d25, m3+d35, m4+d45}=min {10970, 9196, 7896, 8600}=7896

Como esta el program pienso que seria agregarle algo en la mitad del programa pero tengo problemas al trabajar con texto lo que pasa es que quiero mostrar exactamente igual a lo anterior y no se la forma exacta.

2)Agregar la restriction que indique que puntos estan conectados con cual ejemplo: Si el punto 2 no esta conectado con el punto 3 entonces no existe d(2,3) por lo tanto no se evalua esa distancia y se pasa a la distancia entre 2 y 4 es decir d(2,4) si es que existiera asi sucesivamente.Se que habria muchas formas de hacerlo pero me gustaria saber cual seria la mas apropiada. Con esto mi programa estaria practicamente terminado por eso serai de gran ayuda cualquier consejo ,ejemplo o aporte que me puedan brindar tu Deachp o algun otro adicto que este interesado en este tema. Estamos en contacto Gracias Cesar Mori Fuentes Estudiante de Ingenieria Industrial Universidad Nacional Mayor de San Marcos