Implementacion en Java del Algoritmo de Dijkstra

Hoy trataré el tema Algoritmo de Dijkstra, tema perteneciente a la teoría de grafos, así que para entender esto debemos repasar primero que es un grafo y los términos que giran alrededor es este, como costumbre más abajo pueden descargar código fuente y ejecutable, adicional en ésta entrada podrán encontrar mi explicación gráfica y paso a paso del Algoritmo de Dijkstra en PDF para que puedan descargar a sus computadores.

Definición de Algoritmo de Dijkstra: El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. (Tomado de Wikipedia).

En palabras propias puedo decir que Algoritmo de Dijkstra nos sirve para determinar el camino mas corto entre dos nodos dados que pertenecen a un grafo.

Algoritmo dijkstra
Clic aqui para descargar 

View more documents from Rey Salcedo

Me tome la tarea de crear una modesta aplicación que me permita graficar un grafo con pesos y determinar la ruta mas corta entre dos nodos dados, he aqui un patallazo:

El funcionamiento es bastante simple:

• Para crear nodo o vértice con clic izquierdo sobre la superficie, luego te pedirá un nombre.
• Para crear aristas, hacer clic izquierdo sobre los nodos o vértices que deseamos unir, luego nos pedirá el peso que debera ser un entero positivo. 
• Para conocer la ruta mas corta por Dijkstra, hacemos clic derecho sobre el primer nodo y luego clic derecho sobre el segundo nodo.

Adjunto ejecutable, y como siempre esperando serles de utilidad.

Clic aquí para descargar ejecutable.

Pagar codigo fuente

Tambien te puede interesar "Explicación gráfica sobre el Algoritmo de Dijkstra"

Generar números aleatorios sin repetirse en java (usando Math.random)

Saludos a todos,

Este problema me llega a causa de otro problema que estoy solucionando y que posteriormente publicare aquí.

Se trata de generar números aleatorios en java dado un numero inicial y uno final pero con la condición de no repetirse; por ejemplo

numero inicial = 3

numero final = 7

La salida puede ser algo así [6,7,4,5,3]

La forma particular en que lo resuelvo es ir llenando una lista con los numero que voy generando y para así tener una referencia y no repetirlos.

Antes de empezar con el algoritmo tengo que tener en cuenta cuantos numeros como maximo debo generar asi seria (numeroInicial - numeroFinal) + 1; usando el ejemplo anterior quedaría que la máxima cantidad de numero que generare sera (7 - 3) + 1 = 5

El algoritmo para generar un sera así:

1. Si el tamaño de la lista es menor que ((numeroInicial - numeroFinal) + 1) sigo al paso 2, sino al paso 3.

2. Genero un numero aleatorio establecido dentro del rango y sigo al paso 3.

3. Si la lista esta vacía sigo al paso 4 sino al paso 5

4. Adjunto el numero a la lista y sigo al paso 6.

5 Como no esta vacía la lista verifico, si el numero generado esta en la lista regreso al paso 1, sino regreso al paso 4

6. Muestro el numero generado, sigo al paso 7.

7. Fin

Codigo:

//Por Rey Salcedo
import java.util.ArrayList;
public class NumeroAleatorios {
  private int valorInicial;
  private int valorFinal;
  private ArrayList listaNumero;

  public NumeroAleatorios(int valorInicial, int valorFinal){
    this.valorInicial = valorInicial;
    this.valorFinal = valorFinal;
    listaNumero = new ArrayList();
  }
    
  private int numeroAleatorio(){
    return (int)(Math.random()*(valorFinal-valorInicial+1)+valorInicial);
  }
    
  public int generar(){
   if(listaNumero.size() < (valorFinal - valorInicial) +1){
   //Aun no se han generado todos los numeros
      int numero = numeroAleatorio();//genero un numero
      if(listaNumero.isEmpty()){//si la lista esta vacia
        listaNumero.add(numero);
        return numero;
      }else{//si no esta vacia
        if(listaNumero.contains(numero)){//Si el numero que generé esta contenido en la lista
          return generar();//recursivamente lo mando a generar otra vez
        }else{//Si no esta contenido en la lista
          listaNumero.add(numero);
          return numero;
        }
      }
   }else{// ya se generaron todos los numeros
     return -1;
   }
  }
}

public class Ejemplo{
 public static void main(String[] args){
 //Generando números aleatorios del 3 al 7 sin repetirse
  NumeroAleatorios na = new NumeroAleatorios(3,7);   
  for(int i = 0; i < 5;i++){
    System.out.print(na.generar()+",");
  }
 }
}

Nota: si forzar a generar mas numero de los que debería generar te retornara un -1, que te indicará que ya se generaron todos los números posibles.  

Clic aquí para descargar código Ejemplo.java.

Clic aquí para descargar código NumeroAleatorios.java.

Como siempre, espero les guste y les sirva; comenten cualquier duda o sugerencia.