Alguien Podria explicarme el funcionamiento del algoritmo de dijkstra distribuido
Montoya
30 de Noviembre del 2004
Explicacion sobre el funcionamiento general
zodman
30 de Noviembre del 2004
alguien tiene el codigo fuente de esta algoritmos ??
o el codigo en c ????
o el codigo en c ????
Somebody!!
30 de Noviembre del 2004
Primero mujer.. que algoritmo de Dijkstra rekieres??? El de la ruta más corta o El algoritmo sobre exclusión mutua de n procesos????
Somebody!!
30 de Noviembre del 2004
El correcto funcionamiento de un sistema distribuido se puede percibir como la conservacio'n de unainvariante sobre el estado global del sistema. En ese caso se puede decir que el sistema esta' en un estado legal o legi'timo. De lo contrario, el estado del sistema es ilegal. Un sistema auto-estabilizante es aquelque, a partir de un estado arbitrario (posiblemente ilegal), siempre alcanza un estado legal en un nu'mero finito de pasos. Hasta la fecha se ha realizado varios estudios sobre la auto-estabilizacio'n y la exclusio'n mutua paraalgunas topologi'as de sistemas distribuidos como son anillos y a'rboles. Este trabajo propone una
modificacio'n al algoritmo auto-estabilizante de Dijkstra de K > n estados (para n + 1 ma'quinas), con elobjetivo de aplicarlo en procesadores distribuidos en forma de anillo con cuerdas, y obtener ma's ra'pidamente una estabilizacio'n del sistema y una disminucio'n del uso posiblemente erro'neo de la seccio'ncri'tica, en comparacio'n con la topologi'a so'lo de anillo.
Introduccio'n En 1973, Edsger W. Dijkstra introdujo la idea de auto-estabilizacio'n de sistemas. E'l definio' un sistemacomo auto-estabilizante cuando "sin importar el estado inicial, esta' garantizado que el mismo arribe a un
estado legi'timo en un nu'mero finito de pasos" [7]. Esta propiedad es muy deseable para cualquier sistemadistribuido, ya que luego de cualquier perturbacio'n inesperada que modifique el estado del sistema, e'ste se recupera y retorna a un estado legi'timo, sin ninguna intervencio'n externa [14]. Para que esto se cumpla,es necesario que el peri'odo de tiempo entre una recuperacio'n y la pro'xima perturbacio'n sea suficientemente grande [10]. Un sistema que no es auto-estabilizante puede permanecer en un estadoilegi'timo para siempre [16].
El estado de un sistema se considera como el producto cartesiano de los estados de cada uno de losprocesadores individuales que forman el sistema [7]. Dado esto y teniendo en cuenta la posibilidad de que ocurran alteraciones en los estados individuales debido a mensajes corruptos u operaciones incorrectas delos procesadores, el estado global se puede transformar y llegar a una situacio'n ilegi'tima. Por ejemplo, si una ma'quina falla y se reinicia, su estado local puede causar un estado global ilegi'timo. La auto-estabilizacio'n permite el disen~o de sistemas distribuidos ma's robustos. La habilidad de auto-recuperacio'n desde un estado ilegi'timo permite a un sistema ser resistente a fallas o perturbaciones
transitorias e impredecibles que alteren el estado del sistema. Por tanto, los sistemas auto-estabilizantesson ma's confiables y deseables que los no auto-estabilizantes.
Dijkstra propuso soluciones para mantener la exclusio'n mutua en el acceso a una seccio'n cri'tica de unsistema de procesadores distribuidos en forma de anillo [7]. Posteriormente se ha propuesto soluciones para otras topologi'as, como son a'rboles [12] y grafos [16, 1], y para otros problemas, como la coloracio'nde grafos [13, 17], la sincronizacio'n de relojes [9, 4, 11] y la construccio'n de a'rboles de cobertura de grafos [2, 5].
Modelo de Dijkstra En el modelo de Dijkstra, el sistema consiste de un conjunto de n+1 ma'quinas con un nu'mero finito deestados y conectadas en forma de anillo unidireccional. E'l define el privilegio de una ma'quina como la
capacidad para cambiar su propio estado. Esta habilidad de cada ma'quina se basa en una condicio'n quedepende de su estado actual y del estado de su vecina anterior.
Se considera que el sistema se encuentra en un estado legi'timo cuando so'lo una ma'quina posee elprivilegio. Esta definicio'n es una forma de exclusio'n mutua debido a que la existencia de so'lo un privilegio implica que la ma'quina que tiene el privilegio es la que puede estar en la seccio'n cri'tica. Luego,cuando e'sta abandona la seccio'n cri'tica, permite que so'lo la vecina posterior obtenga el privilegio.
Otro asunto importante en el modelo es el nu'mero de estados K que cada ma'quina puede tener. Lasolucio'n original de Dijkstra se basa en que K > n. Adema's, se diferencia una ma'quina de las dema's para romper la simetri'a ci'clica que puede ocurrir si elnu'mero de ma'quinas no es primo. Luego, siendo E el estado actual de una ma'quina y EA el estado de la vecina anterior en el anillounidireccional, el algoritmo es el siguiente: - Para la ma'quina excepcional:
if EA = E then E := (E + 1) mod K fi
- Para las otras ma'quinas:
if EA z' E then E := EA fi
El algoritmo es simple y su correctitud ha sido probada formalmente [8]. Pero, en un anillo con unnu'mero grande de procesadores, la distancia entre muchos de ellos puede resultar muy grande, es decir, la comunicacio'n se hace lenta y por tanto la estabilizacio'n del sistema demorar mucho en alcanzarse. Estatopologi'a tiene adema's el inconveniente de poseer una pobre confiabilidad (cualquier falla en un enlace o procesador puede desconectar la red) [15].
Un anillo con cuerdas Una manera de mejorar la situacio'n anterior es aumentar el grado del nodo (ma'quina). El grado del nodoes el nu'mero de enlaces de un nodo con otros. En un anillo, todos los nodos tienen grado dos. Agregando
un tercer enlace en cada nodo, de forma regular, se puede agilizar la comunicacio'n mediante atajos [3,15]. Asi', se obtiene una estructura de anillo con enlaces adicionales llamados cuerdas.
Un grafo es con cuerdas si y so'lo si cada ciclo (x0...xkx0) de longitud mayor que 3 tiene un enlace entredos nodos no consecutivos del ciclo, es decir, si cada ciclo de longitud mayor que 3 tiene una cuerda [6]. Estas redes tienen un nu'mero par de nodos (m) los cuales pueden designarse con los enteros 0, 1, 2, ...,m -1 [15]. La figura 1 muestra un ejemplo con 10 nodos.
Fig. 1: Ejemplo de anillo con cuerdas con 10 nodos y ciclos de longitud 4. Ana'lisis y modificacio'n del modelo para aplicarlo en un anillo con cuerdas Antes de plantear la modificacio'n propuesta, es necesario sen~alar que al igual que en el anillo de Dijkstraen que la comunicacio'n ocurre so'lo en un sentido, la comunicacio'n a trave's del anillo sera' en un solo
sentido pero a trave's de las cuerdas puede ser en ambos sentidos. El ana'lisis y algoritmo propuestos sebasan en la utilizacio'n de la ma'quina excepcional como la nu'mero 0 y el sentido de comunicacio'n por el anillo desde las ma'quinas con menor nu'mero a las de mayor nu'mero, al igual que en la solucio'n deDijkstra [7].
Adema's, es natural analizar las siguientes situaciones:
- Si un nodo detecta a lo ma's dos estados diferentes (entre e'l y los otros nodos con los que tieneconexio'n), no se puede asegurar que el sistema esta' en un estado ilegi'timo.
- Si un nodo detecta que existe ma's de dos estados en el sistema entonces el sistema esta' en unestado ilegi'timo y el nodo debe cambiar su estado. En este caso el nodo, aunque cambio' su estado,
no debe "creer" que e'l es privilegiado. Para hacer uso del privilegio debe esperar a la pro'xima vezque cambie su estado bajo una situacio'n supuestamente legi'tima del sistema.
Basado en lo anterior, se define, al igual que en el modelo de Dijkstra, a E como el estado actual de unnodo y E
A el estado del vecino anterior en el anillo. Adema's, se define a EC como el estado del vecino dela cuerda.
Se propone el uso de dos estados diferenciados adicionales, uno para indicar deteccio'n de falla y el otropara indicar reinicio. El estado de deteccio'n de falla se propaga desde la ma'quina que detecte una falla, hacia las dema's, a trave's de los enlaces del anillo y de las cuerdas, pero al llegar a la ma'quinaexcepcional, e'sta cambia su estado a reinicio, el cual es propagado a todas las ma'quinas so'lo por los enlaces del anillo. Son necesarios dos estados adicionales porque si la ma'quina excepcional, al enterarse de que ocurrio' unafalla, cambia su estado para el pro'ximo valor va'lido, entonces ella y las que le siguen hasta la anterior a
donde ocurrio' la falla, pueden estar usando el privilegio al igual que la ma'quina donde ocurrio' la falla olas posteriores hasta donde se detecto' la falla, pues nada garantiza que e'stas u'ltimas ya no este'n cambiando sus estados y por tanto usando el privilegio. De esta forma, el estado de deteccio'n de fallapermite que se propague ra'pidamente la noticia de ocurrencia de falla a trave's de todos los enlaces disponibles, mientras el estado de reinicio se va difundiendo so'lo por el anillo, sin cuerdas, para que asi' alllegar hasta la ma'quina anterior a la excepcional es seguro (si no ocurrio' otra falla en el intertanto) que todas las ma'quinas ya han sido reiniciadas y entonces la ma'quina excepcional puede cambiar su estadonormalmente y comenzar a usar el privilegio (seccio'n cri'tica).
Como consecuencia de la propuesta de dos estados nuevos, es necesaria la restriccio'n de que el nu'mero deestados (K) cumpla con K > n + 2. Concretamente, se puede utilizar los estados "0" y "1" para representar el estado de deteccio'n de falla yde reinicio, respectivamente. Adema's, la ma'quina excepcional nunca toma el estado 0 (deteccio'n de falla), excepto debido a una falla interna que altere su estado asigna'ndole dicho valor. Luego, el algoritmo es el siguiente:
- Para la ma'quina excepcional:
if E = 0 then
{Esta ma'quina fallo' y al despertar su estado es "0"} E := 1 {Comenzar un proceso de reinicio} else {E z' 0}
if (EA = 0 or EC = 0) and (E z' 1) then
{Recibe la informacio'n de falla detectada} E := 1 {Comenzar un proceso de reinicio} elseif E z' EA and E z' EC and EA z' EC and E z' 1 then
{Deteccio'n de falla. Se han detectado 3 estados diferentes.} E := 1 {Comenzar un proceso de reinicio} elseif E = EA then
{ Tiene el privilegio } E := 2 + ((E - 1) mod (K - 2)) {Cambiar estado} fi fi
- Para las otras ma'quinas:
if (EA = 0 and E z' 0) or (EC = 0 and E > 1) then
{Recibe la informacio'n de falla detectada}E := 0
{Propagar deteccio'n de falla} elseif EA = 1 and E z' 1 thenE := 1
{Propagar proceso de reinicio}elseif EC = 1 and E > 1 thenE := 0
{Deteccio'n de falla:
- en la vecina de la cuerda porque fallo' y desperto' con el estado en "1", o- porque recibe la informacio'n a trave's de la vecina de la cuerda de que
ha comenzado un proceso de reinicio.Esto permite propagar la informacio'n de ocurrencia de falla au'n cuando esta noticia no ha llegado a la vecina anterior.}elseif E = 1 and EA > 2 thenE := 0
{Deteccio'n de falla, la cual ocurrio':
- en esta ma'quina y al despertar su estado es "1", o- en vecina anterior luego de haber comenzado un proceso de reinicio
global.} elseif E z' EA and E z' 0 then
if E z' EC and EA z' EC thenE := 0
{Deteccio'n de falla. Se han detectado 3 estados diferentes.}else
{ Tiene el privilegio } {Cambiar estado} E := EAfi
fi Como se puede ver, las modificaciones realizadas con relacio'n al algoritmo de Dijkstra, han sido paraevitar el uso de los estados "0" y "1" como estados va'lidos y entonces emplearlos para las situaciones de deteccio'n de falla y reinicio, con el objetivo de difundir lo ma's ra'pido posible la noticia de que el sistemaha cai'do en un estado ilegi'timo.
Finalmente es u'til aclarar que el algoritmo anterior ha sido expuesto con e'nfasis descriptivo para brindaruna mejor comprensio'n del mismo, por lo que en una implementacio'n real puede ser optimizado.
Conclusiones y trabajo futuro Con este trabajo se ha encontrado un algoritmo para auto-estabilizar un grupo de procesadoresconectados con una topologi'a de anillo con cuerdas que aprovecha precisamente las conexiones
adicionales para intentar una estabilizacio'n ma's ra'pida. Con el mismo se permite reducir ma's ra'pido elnu'mero de nodos privilegiados ante una perturbacio'n en el sistema. Es decir, se evita el uso posiblemente erro'neo del privilegio (seccio'n cri'tica) en nodos que si' lo hari'an si la topologi'a del sistema fuera so'lo elanillo.
modificacio'n al algoritmo auto-estabilizante de Dijkstra de K > n estados (para n + 1 ma'quinas), con elobjetivo de aplicarlo en procesadores distribuidos en forma de anillo con cuerdas, y obtener ma's ra'pidamente una estabilizacio'n del sistema y una disminucio'n del uso posiblemente erro'neo de la seccio'ncri'tica, en comparacio'n con la topologi'a so'lo de anillo.
Introduccio'n En 1973, Edsger W. Dijkstra introdujo la idea de auto-estabilizacio'n de sistemas. E'l definio' un sistemacomo auto-estabilizante cuando "sin importar el estado inicial, esta' garantizado que el mismo arribe a un
estado legi'timo en un nu'mero finito de pasos" [7]. Esta propiedad es muy deseable para cualquier sistemadistribuido, ya que luego de cualquier perturbacio'n inesperada que modifique el estado del sistema, e'ste se recupera y retorna a un estado legi'timo, sin ninguna intervencio'n externa [14]. Para que esto se cumpla,es necesario que el peri'odo de tiempo entre una recuperacio'n y la pro'xima perturbacio'n sea suficientemente grande [10]. Un sistema que no es auto-estabilizante puede permanecer en un estadoilegi'timo para siempre [16].
El estado de un sistema se considera como el producto cartesiano de los estados de cada uno de losprocesadores individuales que forman el sistema [7]. Dado esto y teniendo en cuenta la posibilidad de que ocurran alteraciones en los estados individuales debido a mensajes corruptos u operaciones incorrectas delos procesadores, el estado global se puede transformar y llegar a una situacio'n ilegi'tima. Por ejemplo, si una ma'quina falla y se reinicia, su estado local puede causar un estado global ilegi'timo. La auto-estabilizacio'n permite el disen~o de sistemas distribuidos ma's robustos. La habilidad de auto-recuperacio'n desde un estado ilegi'timo permite a un sistema ser resistente a fallas o perturbaciones
transitorias e impredecibles que alteren el estado del sistema. Por tanto, los sistemas auto-estabilizantesson ma's confiables y deseables que los no auto-estabilizantes.
Dijkstra propuso soluciones para mantener la exclusio'n mutua en el acceso a una seccio'n cri'tica de unsistema de procesadores distribuidos en forma de anillo [7]. Posteriormente se ha propuesto soluciones para otras topologi'as, como son a'rboles [12] y grafos [16, 1], y para otros problemas, como la coloracio'nde grafos [13, 17], la sincronizacio'n de relojes [9, 4, 11] y la construccio'n de a'rboles de cobertura de grafos [2, 5].
Modelo de Dijkstra En el modelo de Dijkstra, el sistema consiste de un conjunto de n+1 ma'quinas con un nu'mero finito deestados y conectadas en forma de anillo unidireccional. E'l define el privilegio de una ma'quina como la
capacidad para cambiar su propio estado. Esta habilidad de cada ma'quina se basa en una condicio'n quedepende de su estado actual y del estado de su vecina anterior.
Se considera que el sistema se encuentra en un estado legi'timo cuando so'lo una ma'quina posee elprivilegio. Esta definicio'n es una forma de exclusio'n mutua debido a que la existencia de so'lo un privilegio implica que la ma'quina que tiene el privilegio es la que puede estar en la seccio'n cri'tica. Luego,cuando e'sta abandona la seccio'n cri'tica, permite que so'lo la vecina posterior obtenga el privilegio.
Otro asunto importante en el modelo es el nu'mero de estados K que cada ma'quina puede tener. Lasolucio'n original de Dijkstra se basa en que K > n. Adema's, se diferencia una ma'quina de las dema's para romper la simetri'a ci'clica que puede ocurrir si elnu'mero de ma'quinas no es primo. Luego, siendo E el estado actual de una ma'quina y EA el estado de la vecina anterior en el anillounidireccional, el algoritmo es el siguiente: - Para la ma'quina excepcional:
if EA = E then E := (E + 1) mod K fi
- Para las otras ma'quinas:
if EA z' E then E := EA fi
El algoritmo es simple y su correctitud ha sido probada formalmente [8]. Pero, en un anillo con unnu'mero grande de procesadores, la distancia entre muchos de ellos puede resultar muy grande, es decir, la comunicacio'n se hace lenta y por tanto la estabilizacio'n del sistema demorar mucho en alcanzarse. Estatopologi'a tiene adema's el inconveniente de poseer una pobre confiabilidad (cualquier falla en un enlace o procesador puede desconectar la red) [15].
Un anillo con cuerdas Una manera de mejorar la situacio'n anterior es aumentar el grado del nodo (ma'quina). El grado del nodoes el nu'mero de enlaces de un nodo con otros. En un anillo, todos los nodos tienen grado dos. Agregando
un tercer enlace en cada nodo, de forma regular, se puede agilizar la comunicacio'n mediante atajos [3,15]. Asi', se obtiene una estructura de anillo con enlaces adicionales llamados cuerdas.
Un grafo es con cuerdas si y so'lo si cada ciclo (x0...xkx0) de longitud mayor que 3 tiene un enlace entredos nodos no consecutivos del ciclo, es decir, si cada ciclo de longitud mayor que 3 tiene una cuerda [6]. Estas redes tienen un nu'mero par de nodos (m) los cuales pueden designarse con los enteros 0, 1, 2, ...,m -1 [15]. La figura 1 muestra un ejemplo con 10 nodos.
Fig. 1: Ejemplo de anillo con cuerdas con 10 nodos y ciclos de longitud 4. Ana'lisis y modificacio'n del modelo para aplicarlo en un anillo con cuerdas Antes de plantear la modificacio'n propuesta, es necesario sen~alar que al igual que en el anillo de Dijkstraen que la comunicacio'n ocurre so'lo en un sentido, la comunicacio'n a trave's del anillo sera' en un solo
sentido pero a trave's de las cuerdas puede ser en ambos sentidos. El ana'lisis y algoritmo propuestos sebasan en la utilizacio'n de la ma'quina excepcional como la nu'mero 0 y el sentido de comunicacio'n por el anillo desde las ma'quinas con menor nu'mero a las de mayor nu'mero, al igual que en la solucio'n deDijkstra [7].
Adema's, es natural analizar las siguientes situaciones:
- Si un nodo detecta a lo ma's dos estados diferentes (entre e'l y los otros nodos con los que tieneconexio'n), no se puede asegurar que el sistema esta' en un estado ilegi'timo.
- Si un nodo detecta que existe ma's de dos estados en el sistema entonces el sistema esta' en unestado ilegi'timo y el nodo debe cambiar su estado. En este caso el nodo, aunque cambio' su estado,
no debe "creer" que e'l es privilegiado. Para hacer uso del privilegio debe esperar a la pro'xima vezque cambie su estado bajo una situacio'n supuestamente legi'tima del sistema.
Basado en lo anterior, se define, al igual que en el modelo de Dijkstra, a E como el estado actual de unnodo y E
A el estado del vecino anterior en el anillo. Adema's, se define a EC como el estado del vecino dela cuerda.
Se propone el uso de dos estados diferenciados adicionales, uno para indicar deteccio'n de falla y el otropara indicar reinicio. El estado de deteccio'n de falla se propaga desde la ma'quina que detecte una falla, hacia las dema's, a trave's de los enlaces del anillo y de las cuerdas, pero al llegar a la ma'quinaexcepcional, e'sta cambia su estado a reinicio, el cual es propagado a todas las ma'quinas so'lo por los enlaces del anillo. Son necesarios dos estados adicionales porque si la ma'quina excepcional, al enterarse de que ocurrio' unafalla, cambia su estado para el pro'ximo valor va'lido, entonces ella y las que le siguen hasta la anterior a
donde ocurrio' la falla, pueden estar usando el privilegio al igual que la ma'quina donde ocurrio' la falla olas posteriores hasta donde se detecto' la falla, pues nada garantiza que e'stas u'ltimas ya no este'n cambiando sus estados y por tanto usando el privilegio. De esta forma, el estado de deteccio'n de fallapermite que se propague ra'pidamente la noticia de ocurrencia de falla a trave's de todos los enlaces disponibles, mientras el estado de reinicio se va difundiendo so'lo por el anillo, sin cuerdas, para que asi' alllegar hasta la ma'quina anterior a la excepcional es seguro (si no ocurrio' otra falla en el intertanto) que todas las ma'quinas ya han sido reiniciadas y entonces la ma'quina excepcional puede cambiar su estadonormalmente y comenzar a usar el privilegio (seccio'n cri'tica).
Como consecuencia de la propuesta de dos estados nuevos, es necesaria la restriccio'n de que el nu'mero deestados (K) cumpla con K > n + 2. Concretamente, se puede utilizar los estados "0" y "1" para representar el estado de deteccio'n de falla yde reinicio, respectivamente. Adema's, la ma'quina excepcional nunca toma el estado 0 (deteccio'n de falla), excepto debido a una falla interna que altere su estado asigna'ndole dicho valor. Luego, el algoritmo es el siguiente:
- Para la ma'quina excepcional:
if E = 0 then
{Esta ma'quina fallo' y al despertar su estado es "0"} E := 1 {Comenzar un proceso de reinicio} else {E z' 0}
if (EA = 0 or EC = 0) and (E z' 1) then
{Recibe la informacio'n de falla detectada} E := 1 {Comenzar un proceso de reinicio} elseif E z' EA and E z' EC and EA z' EC and E z' 1 then
{Deteccio'n de falla. Se han detectado 3 estados diferentes.} E := 1 {Comenzar un proceso de reinicio} elseif E = EA then
{ Tiene el privilegio } E := 2 + ((E - 1) mod (K - 2)) {Cambiar estado} fi fi
- Para las otras ma'quinas:
if (EA = 0 and E z' 0) or (EC = 0 and E > 1) then
{Recibe la informacio'n de falla detectada}E := 0
{Propagar deteccio'n de falla} elseif EA = 1 and E z' 1 thenE := 1
{Propagar proceso de reinicio}elseif EC = 1 and E > 1 thenE := 0
{Deteccio'n de falla:
- en la vecina de la cuerda porque fallo' y desperto' con el estado en "1", o- porque recibe la informacio'n a trave's de la vecina de la cuerda de que
ha comenzado un proceso de reinicio.Esto permite propagar la informacio'n de ocurrencia de falla au'n cuando esta noticia no ha llegado a la vecina anterior.}elseif E = 1 and EA > 2 thenE := 0
{Deteccio'n de falla, la cual ocurrio':
- en esta ma'quina y al despertar su estado es "1", o- en vecina anterior luego de haber comenzado un proceso de reinicio
global.} elseif E z' EA and E z' 0 then
if E z' EC and EA z' EC thenE := 0
{Deteccio'n de falla. Se han detectado 3 estados diferentes.}else
{ Tiene el privilegio } {Cambiar estado} E := EAfi
fi Como se puede ver, las modificaciones realizadas con relacio'n al algoritmo de Dijkstra, han sido paraevitar el uso de los estados "0" y "1" como estados va'lidos y entonces emplearlos para las situaciones de deteccio'n de falla y reinicio, con el objetivo de difundir lo ma's ra'pido posible la noticia de que el sistemaha cai'do en un estado ilegi'timo.
Finalmente es u'til aclarar que el algoritmo anterior ha sido expuesto con e'nfasis descriptivo para brindaruna mejor comprensio'n del mismo, por lo que en una implementacio'n real puede ser optimizado.
Conclusiones y trabajo futuro Con este trabajo se ha encontrado un algoritmo para auto-estabilizar un grupo de procesadoresconectados con una topologi'a de anillo con cuerdas que aprovecha precisamente las conexiones
adicionales para intentar una estabilizacio'n ma's ra'pida. Con el mismo se permite reducir ma's ra'pido elnu'mero de nodos privilegiados ante una perturbacio'n en el sistema. Es decir, se evita el uso posiblemente erro'neo del privilegio (seccio'n cri'tica) en nodos que si' lo hari'an si la topologi'a del sistema fuera so'lo elanillo.
manuel pertuz
30 de Noviembre del 2004
alguien podria mandarme el algoritmo de dijkstra.........
es urgente les agradezco...................
es urgente les agradezco...................
hugo
30 de Noviembre del 2004
visiten: www.dijkstra.cjb.net
tiene un programa de muestra funcionando
tiene un programa de muestra funcionando
Hugo
30 de Noviembre del 2004
visiten: www.dijkstra.cjb.mx
kalbazita
30 de Noviembre del 2004
NECESITO CON URGENCIA EL CODIGO DEL ALGORITMO DE DIJKSTRA EN PASCAL, NECESITO EL DEL CAMINO MINIMO, OS AGRADECERE....
killer
30 de Noviembre del 2004
El algoritmo de dijkstra funcion sobre grafos. Tiene que ser un grafo conexo.Q es lo q hace a un grafo, con pesos estos es un valor en las aristas, te consigue el grafo conexo cuyo valor de los pesos es menor.