Alguém poderia me ajudar, como encontrar o menor caminho entre dois vértices em um grafo orientado?

Programação Java
,
#1

O programa deve solicitar ao usuário o vértice de partida da rota e o vértice de destino. Em seguida, deve descrever o menor trajeto possível do vértice de partida até o destino. Por exemplo, dado o vértice de partida 2 e o vértice de destino 4 para o grafo abaixo, o programa deve apresentar a saída 2 – 3 – 4.

import java.util.Scanner;

public class shortestPath {

static final int V = 9;

/* Encontra o vértice mais próximo do conjunto de vértices ainda não incluidos na árvore
de menor caminho */
int minDistance(int dist[], Boolean sptSet[]){
	
	// Inicializa o menor valor
	int min = Integer.MAX_VALUE, min_index = -1;

	for (int v = 0; v < V; v++)
		if (sptSet[v] == false && dist[v] <= min) {
			min = dist[v];
			min_index = v;
		}

	return min_index;
}

// Exibe o vetor distancia
void printSolution(int dist[]) {
	System.out.println("Vertex \t\t Distance from Source");
	for (int i = 0; i < V; i++)
		System.out.println(i + " \t\t " + dist[i]);
}

// Imlementa o algoritmo
void dijkstra(int graph[][], int src) {
	// Vetor que possui o resultado. Armazena a distância de cada vértice para a origem.
	//dist[i] possuirá o menor caminho da origem até i.
	int dist[] = new int[V]; 
	
	//sptSet[i] será true se o vértice fizer parte do menor caminho
	//ou se não for possível continuar
	Boolean sptSet[] = new Boolean[V];

	// Inicializa todas as distâncias com o maior valor possível
	//e stpSet[] como false
	for (int i = 0; i < V; i++) {
		dist[i] = Integer.MAX_VALUE;
		sptSet[i] = false;
	}

	// A distância de todo nó para si mesmo é zero
	dist[src] = 0;

	// Encontra o menor caminho para todos os vértices
	for (int count = 0; count < V - 1; count++) {			
		/* Seleciona o vértice com menor distância dos vértices ainda não visitados.
		 * 
		 * u sempre é a origem na primeira iteração.
		 */
		int u = minDistance(dist, sptSet);

		// Marca o vértice como visitado
		sptSet[u] = true;

		/* Atualiza o valor dist dos vértices adjacentes ao vértice selecionado*/			
		for (int v = 0; v < V; v++)				
			/* Atualiza dist[v] apenas se ele não estiver em sptSet, 
			 * existe uma aresta entre u e v, e o peso total do caminho da origem até
			 * o destino é menor do que o atual dist[v]
			 */
			if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && 
			dist[u] + graph[u][v] < dist[v])
				dist[v] = dist[u] + graph[u][v];
	}

	// Exibe o vetor com as distâncias
	printSolution(dist);
}

	public static void main(String[] args) {
		
		int graph [][] = new int[][] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
									{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
									{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
									{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
									{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
									{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
									{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
									{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
									{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
	   
		shortestPath t = new shortestPath();
        Scanner scanner = new Scanner(System.in);
		System.out.println("Digite a vértice de partida:"); 
		int input = scanner.nextInt();
		
		System.out.println("Digite a vértice de destino:"); 
		input = scanner.nextInt();
		
		t.dijkstra(graph, input);
		//t.dijkstra(graph, 0) ;
		scanner.close();
	}
}
Preciso de ajuda nesse codigo que implementa o algoritmo de Dijkstra (Grafo):
#2

Alguém poderia me ajudar, ainda não resolver ?

#3

Alguém poderia me ajudar, ainda não resolver ?

#4

Estás a ler dois valores para a mesma variavel, só o segundo será usado, o primeiro vai ser descartado.

#5

alterei aqui, mas a saída não estar apresentando os valores assim 2 - 3 - 4

#6

O que é um vértice para ti? Tens uma matriz, logo uma posição deveria ser definida com uma coordenada de dois números e não apenas com um número.

#7

então no caso teria que alterar aqui:
// Inicializa o menor valor
int min = Integer.MAX_VALUE, min_index = -1;