/****************************************************
***Algoritmo: Dijkstra (One Source Shortest Path)
****************************************************/
/*
EJEMPLO DE INPUT
59
127
142
231
242
354
423
438
455
535
*/
import [Link].*;
public class DijkstraAlgorithm {
public static void main(String[] args) {
int E , origen, destino , peso , inicial, V;
Scanner sc = new Scanner( [Link] ); //para lectura de datos
[Link]("Ingrese el numero de vertices: ");
V = [Link]();
[Link]("Ingrese el numero de aristas: ");
E = [Link]();
Dijkstra dijkstraAlgorithm = new Dijkstra(V);
for( int i = 0 ; i < E ; ++i ){
origen = [Link](); destino = [Link](); peso = [Link]();
[Link](origen, destino, peso, true);
[Link]("Ingrese el vertice inicial: ");
inicial = [Link]();
[Link](inicial);
[Link]();
class Dijkstra{
//similar a los defines de C++
private final int MAX = 10005; //maximo numero de vértices
private final int INF = 1<<30; //definimos un valor grande que represente la distancia infinita inicial,
basta conque sea superior al maximo valor del peso en alguna de las aristas
private List< List< Node > > ady = new ArrayList< List< Node > >(); //lista de adyacencia
private int distancia[ ] = new int[ MAX ]; //distancia[ u ] distancia de vértice inicial a vértice con ID
=u
private boolean visitado[ ] = new boolean[ MAX ]; //para vértices visitados
private PriorityQueue< Node > Q = new PriorityQueue<Node>(); //priority queue propia de Java,
usamos el comparador definido para que el de menor valor este en el tope
private int V; //numero de vertices
private int previo[] = new int[ MAX ]; //para la impresion de caminos
private boolean dijkstraEjecutado;
Dijkstra(int V){
this.V = V;
for( int i = 0 ; i <= V ; ++i )
[Link](new ArrayList<Node>()) ; //inicializamos lista de adyacencia
dijkstraEjecutado = false;
//En el caso de java usamos una clase que representara el pair de C++
class Node implements Comparable<Node>{
int first, second;
Node( int d , int p ){ //constructor
[Link] = d;
[Link] = p;
public int compareTo( Node other){ //es necesario definir un comparador para el correcto
funcionamiento del PriorityQueue
if( second > [Link] ) return 1;
if( second == [Link] ) return 0;
return -1;
};
//función de inicialización
private void init(){
for( int i = 0 ; i <= V ; ++i ){
distancia[ i ] = INF; //inicializamos todas las distancias con valor infinito
visitado[ i ] = false; //inicializamos todos los vértices como no visitados
previo[ i ] = -1; //inicializamos el previo del vertice i con -1
}
}
//Paso de relajacion
private void relajacion( int actual , int adyacente , int peso ){
//Si la distancia del origen al vertice actual + peso de su arista es menor a la distancia del origen al
vertice adyacente
if( distancia[ actual ] + peso < distancia[ adyacente ] ){
distancia[ adyacente ] = distancia[ actual ] + peso; //relajamos el vertice actualizando la distancia
previo[ adyacente ] = actual; //a su vez actualizamos el vertice previo
[Link]( new Node( adyacente , distancia[ adyacente ] ) ); //agregamos adyacente a la cola de
prioridad
void dijkstra( int inicial ){
init(); //inicializamos nuestros arreglos
[Link]( new Node( inicial , 0 ) ); //Insertamos el vértice inicial en la Cola de Prioridad
distancia[ inicial ] = 0; //Este paso es importante, inicializamos la distancia del inicial como 0
int actual , adyacente , peso;
while( ![Link]() ){ //Mientras cola no este vacia
actual = [Link]().first; //Obtengo de la cola el nodo con menor peso, en un comienzo
será el inicial
[Link](); //Sacamos el elemento de la cola
if( visitado[ actual ] ) continue; //Si el vértice actual ya fue visitado entonces sigo sacando
elementos de la cola
visitado[ actual ] = true; //Marco como visitado el vértice actual
for( int i = 0 ; i < [Link]( actual ).size() ; ++i ){ //reviso sus adyacentes del vertice actual
adyacente = [Link]( actual ).get( i ).first; //id del vertice adyacente
peso = [Link]( actual ).get( i ).second; //peso de la arista que une actual con adyacente (
actual , adyacente )
if( !visitado[ adyacente ] ){ //si el vertice adyacente no fue visitado
relajacion( actual , adyacente , peso ); //realizamos el paso de relajacion
[Link]( "Distancias mas cortas iniciando en vertice %d\n" , inicial );
for( int i = 1 ; i <= V ; ++i ){
[Link]("Vertice %d , distancia mas corta = %d\n" , i , distancia[ i ] );
dijkstraEjecutado = true;
void addEdge( int origen , int destino , int peso , boolean dirigido ){
[Link]( origen ).add( new Node( destino , peso ) ); //grafo diridigo
if( !dirigido )
[Link]( destino ).add( new Node( origen , peso ) ); //no dirigido
void printShortestPath(){
if( !dijkstraEjecutado ){
[Link]("Es necesario ejecutar el algorithmo de Dijkstra antes de poder imprimir el
camino mas corto");
return;
Scanner sc = new Scanner( [Link] ); //para lectura de datos
[Link]("\n**************Impresion de camino mas corto**************");
[Link]("Ingrese vertice destino: ");
int destino;
destino = [Link]();
print( destino );
[Link]("\n");
//Impresion del camino mas corto desde el vertice inicial y final ingresados
void print( int destino ){
if( previo[ destino ] != -1 ) //si aun poseo un vertice previo
print( previo[ destino ] ); //recursivamente sigo explorando
[Link]("%d " , destino ); //terminada la recursion imprimo los vertices recorridos
public int getNumberOfVertices() {
return V;
public void setNumberOfVertices(int numeroDeVertices) {
V = numeroDeVertices;