Define the smallest path in graphs

Question

Define the smallest path in graphs

Navigation

#1 by (2 votes)

2

Hello, I'm starting to see graphs now, I'm trying to create a program where the user enters an adjacency array and the program calculates the smallest possible path from the start node to the end and that all the edges have the same weight, but I could not find a way for the program to know that it has reached the last node, so I will compare it with the auxiliary variable to know 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 a lot of shit talk, I'm studying on my own)

java matriz path

asked by anonymous 09.08.2016 / 02:23

1 answer

Treat Javascript Postback SVG icon created with Inkscape is not properly imported

score 2 · Accepted Answer

Finding the smallest path in a graph is a bit more complex than that.

In your case where all the edges have the same weight you can use a width search. The following code is an example of using the width search to find the smallest 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 function ma was made only to access the adjacency matrix on the same side (since it is usually symmetric, if not remove 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 how well the width search occurs:

The algorithm starts at the initial node with value 1. This node adds all its neighbors in the queue and places value 2 in all. The next node in the queue adds all its neighbors that have no value in the queue and places their values as 3. The algorithm continues until all the nodes in the queue have finished. The last nodes do not add anyone in the queue, since all their neighbors will already have value. So at some point the nodes are gone and the queue goes empty until it is completely empty, finishing the algorithm.

Note that the proposed algorithm only has the difference that the first node receives a value of zero 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 the nodes are not all the same then a variation of the search in width is called Dijkstra's algorithm.