Esta solução considera o algoritmo de Dijkstra e com uma pequena alteração foi possível pegar os caminhos da mesma forma que os calcula.
Deve haver codificações melhores, pois eu comecei a entender as instruções do código faz poucos dias apenas por curiosidade, além de não ser profissional da área, mas a codificação esta funcional e explicada.
Assim, estou compartilhando a codificação em java para que possa ser comparada com outras.
Classe de teste
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import javax.swing.JFrame;
public class Crisis extends JFrame {
public static void main(String[] args) {
ArrayList<Vertice> grafo = new ArrayList<>();
//adicionando os vétices ao grafo
Collections.addAll(grafo, new Vertice("A"),new Vertice("B"),new Vertice("C"),
new Vertice("D"),new Vertice("E"),new Vertice("F"),new Vertice("G"));
float ponteBC, ponteCD;//NÃO é um problema mas preferi criar "pontes" para evitar caminhos "duplos"
//gerando as arestas
arestar(grafo.get(0), new Aresta("B", dist()), new Aresta("D", dist()));//A "aponta" para B e C
arestar(grafo.get(1), new Aresta("F", dist()), new Aresta("C", ponteBC = dist()));//B para F e C
arestar(grafo.get(2), new Aresta("B", ponteBC), new Aresta("D", ponteCD = dist()));//C para B e D
arestar(grafo.get(3), new Aresta("C", ponteCD), new Aresta("E", dist()));//para D
arestar(grafo.get(4), new Aresta("G", dist()));//E aponta para G
arestar(grafo.get(5), new Aresta("G", dist()));//F aponta para G que nãp aponta para ninguém
//procurando o menor caminho, a origem é A na posição 0 e destino é G não posição 6, neste exemplo
Vertice.menorCaminho(grafo.get(0), grafo.get(6), grafo);
}
//método para auxiliar o preenchimento
private static void arestar(Vertice vertice, Aresta ... arestas){
vertice.getArestas().addAll(Arrays.asList(arestas));
}
//para auxiliar na distância aleatória
private static float dist(){
return new Random().nextInt(25) + 5;
}
}
Classe que representará os vértices do grafo:
import java.util.ArrayList;
import java.util.Collections;
import javax.swing.JOptionPane;
public class Vertice implements Comparable<Vertice> {
private final String referencia;
private float peso;
private final ArrayList<Aresta> arestas = new ArrayList<>();
private String caminho = null;
public Vertice(String referencia) {
this.referencia = referencia;
}
public String getReferencia() {
return referencia;
}
public float getPeso() {
return peso;
}
public void setPeso(float peso) {
this.peso = peso;
}
public ArrayList<Aresta> getArestas() {
return arestas;
}
@Override//vai nos ajudar a identifica o menor peso usando o método sort (ordenar em ordem crescente)
public int compareTo(Vertice outroVertice) {
return Float.compare(peso, outroVertice.peso);
}
public static void menorCaminho(Vertice origem, Vertice destino, ArrayList<Vertice> grafo) {
//primeiro todos os pesos do grafo são declarados como o maior valor possível
grafo.forEach(vertice -> {
vertice.peso = Float.POSITIVE_INFINITY;
});
//a variável origem deve estar contida no grafo e o peso dela é inicializado com 0
origem.setPeso(0);
origem.caminho = origem.referencia;//inicializando o caminho
//vamos precisar de SOMENTE uma lista para atualizar o peso dos vértices
ArrayList<Vertice> fila = new ArrayList<>(grafo);//todos os vertices foram adicionados à "FILA"
//enquanto houver elementos na fila removemos o elemento com o menor peso e atualizamos os demais
while (!fila.isEmpty()) {
Vertice menor = verticeMaisLeve(fila);
//vamos procurar os vertices vizinhos utilizando a referência como parâmetro
for (Aresta aresta : menor.getArestas()) {//para cada aresta
for (Vertice vertice : grafo) {//verificamos cada vertice no grafo, ou seja não verifico a fila e sim o grafo
if (vertice.getReferencia().equals(aresta.getReferencia())) {//filtro para atualização dos pesos pela referencia
if (vertice.peso > menor.peso + aresta.getDistancia()) {
vertice.setPeso(menor.peso + aresta.getDistancia());
vertice.caminho = menor.caminho + " > " + vertice.referencia;
}
break;
}
}
}
}
JOptionPane.showMessageDialog(null, "MENOR CAMINHO DE "+origem.getReferencia()+" a "
+ destino.referencia+"\n"+(destino.caminho == null? "As cidades não se comunicam ":destino.caminho)+" \n");
}
private static Vertice verticeMaisLeve(ArrayList<Vertice> fila) {
//como implementamos o comparable, podemos usar ordenar a coleção com ferramentas do java
Collections.sort(fila);//ordenando a fila de acordo com o peso de cada vétice
return fila.remove(0);//retornamos o menor elemento da fila e o removemos da fila (obs.: em uma instrução)
}
}
Classe que representará as arestas do grafo
public class Aresta {
private final String referencia;
private final float distancia;
public Aresta(String referencia, float distancia) {
this.referencia = referencia;
this.distancia = distancia;
}
public float getDistancia() {
return distancia;
}
public String getReferencia() {
return referencia;
}
}