GRAFOS: IMPLEMENTACION ALGORITMO DIJKSTRA EN JAVA

En este articulo veremos una implementacion de código del algoritmo dijkstra en java. En la parte final podran encontrar el codigo fuente.

Código en java para el algoritmo Dijkstra

En el día de hoy les traigo el algoritmo de Dijkstra en java (implementacion por el método de matriz de adyacencia).
Un poco de historia sobre la palabra Dijkstra, por su no lo sabes, es el apellido del creador del algoritmo antes mencionado.
Si estas en este mundo de la informática es casi que cultura general que sepas quien es Edsger Dijkstra.

Edsger Dijkstra

Dijkstra es conocido como un "personaje" en el mundo de las ciencias de la computación, quizas uno de los más grandes, diría yo. Gran parte de sus artículos y libros no tienen ninguna referencia, pues él se consideraba autónomo. Esta ausencia de referencias fue criticada por muchos investigadores. Años más tarde la mayoría de científicos  computaciones lo citarían en miles de artículos y papers alrededor del mundo.

Aunque parezca irónico, Dijkstra, uno de los mayores desarrolladores del software de su época, evitó el uso de computadores en su trabajo durante décadas. Cuando, finalmente, sucumbió a la tecnología, únicamente utilizó los ordenadores para enviar correos electrónicos y hacer búsquedas en la red. Dijkstra nunca utilizó un computador para realizar ninguno de sus trabajos, todos ellos fueron realizados a mano.

Desde una edad muy temprana destacó por su ingenio y elocuencia. Cuando era pequeño le aseguró a su madre que no resolvería ningún problema o cuestión que le ocupará más de cinco líneas de un folio.

Dijkstra también destacó como escrito de ensayos. En uno de ellos, en tono humorístico describió una empresa ficticia en la que había trabajado como presidente llamada Mathematics. Inc. Esta empresa se había dedicado a comercializar teoremas matemáticos (un paralelismo a lo que estaba ocurriendo con las empresas tecnológicas, las cuales estaban haciendo una abusiva comercialización de los programas que desarrollaban). Al concluir este discurso Dijkstra aseguró que era la empresa más emocionante, y a la vez miserable jamás concebida.

Recordemos que se debe crear una clase llamada Main para que no te marque ningún error.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

/**
* Solucion por matriz de adyacencia
*
* @author GUERRERO
*
*/
public class Main {

private static int matrix[][];
private static int maxvertices;
private static int maxaristas;
private static int aristas;

/**
* Cramos en grafo
*
* @param nVertices
* @param nAristas
*/
public static void crearGrafo(int nVertices, int nAristas) {
maxvertices = nVertices;
maxaristas = nAristas;
aristas = 0;
matrix = new int[maxvertices][maxvertices];
}

/**
* Insertar arista
*
* @param v1
*            vertice 1
* @param v2
*            vertice 2
* @param dist
*            distancia entre cada vertice
*/
public static void insertaArista(int v1, int v2, int dist) {
if (v1 >= maxvertices || v2 >= maxvertices) {
throw new ArrayIndexOutOfBoundsException(
"Vertices inválidos, fuera de rango" + "nRango de vertices: 0 - " + (maxvertices - 1));
} else if (aristas == maxaristas) {
throw new UnsupportedOperationException("No se puede añadir más aristas");
} else {
matrix[v1][v2] = dist;
matrix[v2][v1] = dist;
}
}

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


String temp []=br.readLine().split(" ");
int vertices = Integer.parseInt(temp[0]);
int aristas = Integer.parseInt(temp[1]);
// crea el grafo y lo llena
crearGrafo(vertices, aristas);
for (int i = 0; i < vertices; i++) {
String temp2 [] =br.readLine().split(" ");
insertaArista(Integer.parseInt(temp2[0]), Integer.parseInt(temp2[1]), Integer.parseInt(temp2[2]));
}

//en este caso calcula la distancia minima entre el nodo 0 y el 2
System.out.println(dijkistra(0)[2]);
}

/**
* Calcula la distancia mas corta.
* @param inicio nodo desde donde se va a iniciar.
* @return
*/
public static int[] dijkistra(int inicio) {
int[] distancia = new int[maxvertices];
int[] padre = new int[maxvertices];
boolean[] visto = new boolean[maxvertices];
for (int i = 0; i < maxvertices; i++) {
distancia[i] = 1200000000;
padre[i] = -1;
visto[i] = false;
}
distancia[inicio]=0;
PriorityQueue<Integer> pila = new PriorityQueue<>();
pila.add(distancia[inicio]);
while (!pila.isEmpty()) {
int u = pila.poll();
visto[u] = true;
for (int i = 0; i < maxvertices; i++) {
if (matrix[u][i] != 0) {
// aqui es donde se debe tratar de editar para que nos incluya el parametro gas que es un arreglo de strings
if (distancia[i] > distancia[u] + matrix[u][i]) {
distancia[i] = distancia[u] + matrix[u][i];
padre[i] = u;
pila.add(i);
}
}
}
}
return distancia;
}

}