Set the shortest path in graphs

Question

Hello, I’m starting to see graphs now, I’m trying to create a program where the user enters with an adjacency matrix and the program calculates the shortest possible path from the initial node to the end and that all edges have the same weight, but I couldn’t find a way for the program to know that it reached the last node, so I’ll compare it to the auxiliary variable to know which is the shortest path

I’ve done this so far:

static int tCaminho = 100, tAux = 0;
static int[][] ma = new int[8][8];
static Scanner scan = new Scanner(System.in);

public static void main(String[] args) {
    // TODO Auto-generated method stub

    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            ma[i][j] = scan.nextInt();
        }
    }

    caminho(0 , 0);
    System.out.println(tCaminho);
}

public static void caminho(int c, int cc){
    for(int j = cc; j < 8; ++j){
        if(ma[c][j] == 1){
            ++tAux;
            caminho(c+1, 0);
        }

        if(j == 7){
            if(tAux < tCaminho){
                tCaminho = tAux;
            }
            tAux = 0;
        }
    }
}

Someone could help (if you’re doing too much shit talk, I’m studying on my own)

Answer 1

Finding the shortest path in a graph is a little more complex than this.

In your case where all edges have the same weight it is possible to use a search in width. The following code is an example of using the width search to find the shortest path to all vertices.

public static int[] buscaLateral(int inicio, int[][] ma, int tam){
    int[] distancias = new int[tam];
    Queue<Integer> fila = new LinkedList<Integer>();

    // Inicializando a menor distância de todos os vértices ao inicial como -1
    for(int i=0; i<8; i++)
        distancias[i]=-1;

    // A distância do vértice inicial a ele mesmo é zero
    distancias[inicio] = 0;
    fila.add(inicio);

    // Executando a busca lateral
    while(!fila.isEmpty()){
        int atual = fila.remove();
        for(int i = 0; i < 8; i++)
            if(ma(atual, i, ma) == 1 && distancias[i] == -1){
                distancias[i] = distancias[atual] + 1;
                fila.add(i);
            }
    }
    return distancias;
}

See the full code on Ideone.

The ma function was only done to access the adjacency matrix on the same side (because it is usually symmetric if it is not take the if from the function):

public static int ma(int i, int j, int[][] ma){
    if(i < j)
        return ma[i][j];
    else
        return ma[j][i];
}

Here is an image that explains well how the search in width occurs:

The algorithm starts at the initial node with value 1. This node adds all its neighbors in the queue and puts value 2 in all. The next node in the queue adds all its neighbors that still have no value in the queue and sets their values to 3. The algorithm continues until all nodes in the queue are gone. The last nodes don’t add anyone in the queue, since all your neighbors will already have value. So at a certain point the nodes end and the queue empties until it is completely empty finishing the algorithm.

Note that the proposed algorithm only has the difference that the first node receives zero value and so the value of each node is already the shortest distance to the first node. This algorithm only works because all distances are equal. If the distances between nodes are not all the same, a variation of the search in width that is called the Dijkstra algorithm should be used.