¿Dónde puedo obtener una implementación de Java del algoritmo de Dijkstra?

Estoy buscando una implementación Java genérica del algoritmo de Dijkstra. He intentado codificar esto por mi cuenta, pero sigo teniendo problemas. Si ayuda, sé de hecho que el gráfico siempre está conectado. ¿Alguien sabe de tal implementación?¿Dónde puedo obtener una implementación de Java del algoritmo de Dijkstra?

Gracias!

Fuente

2011-08-25 MozenRath

Esto es totalmente desvergonzado, pero codifiqué una implementación del algoritmo de Dijkstra usando montones de Fibonacci hace un tiempo y lo publiqué en mi sitio web personal. Puede encontrar el código aquí:

He tratado de comentar el código para indicar cómo funciona el algoritmo, qué supuestos se trata de hacer, etc., así que espero que es Fácil de leer y entender. Avíseme si hay algo al respecto que pueda aclararle.

Espero que esto ayude!

Fuente

2011-08-25 21:28:47 templatetypedef

que necesitaba para la sencilla sin dirección gráfico conectado s :) – MozenRath

@ Piyush: puede representar un gráfico no dirigido utilizando un gráfico dirigido: simplemente haga que cada par de nodos conectados apunten entre sí. – templatetypedef

@templatetypedef En mi opinión, su código es el más limpio que he visto en la red para dijkstra, ¿podría compartir también el enlace de DirectedGraph que pasa como argumento? – JavaDeveloper

Qué quiere decir esto:

(la aplicación Java se puede encontrar en enlace mencionado (véase la parte inferior de esta respuesta)

// initialize d to infinity, π and Q to empty 
d = (∞) 
π =() 
S = Q =() 

add s to Q 
d(s) = 0 

while Q is not empty 
{ 
    u = extract-minimum(Q) 
    add u to S 
    relax-neighbors(u) 
} 

relax-neighbors(u) 
{ 
    for each vertex v adjacent to u, v not in S 
    { 
      if d(v) > d(u) + [u,v] // a shorter distance exists 
      { 
       d(v) = d(u) + [u,v] 
       π(v) = u 
       add v to Q 
      } 
    } 
} 

extract-minimum(Q) 
{ 
    find the smallest (as defined by d) vertex in Q 
    remove it from Q and return it 
}

edición: conseguido esto desde http://renaud.waldura.com/doc/java/dijkstra/

Fuente

2011-08-25 21:29:33

Eso no está compilando en mi versión de java. ¿Qué versión estás usando? – Patrick87

Creo que el OP busca específicamente el código de Java en lugar de pseudocódigo; la pregunta sugiere que el OP ha encontrado pseudocódigo pero tiene problemas para traducirlo a Java. – templatetypedef

la implementación de Java se puede encontrar en el enlace :) –

JGrapht es una biblioteca común de Java para gráficos. También se implementa el algoritmo de dijkstra.

Fuente

2011-08-25 21:30:57 Heisenbug

Buenos recursos de Universidades