Dijkstra's print algorithm

I am trying to make my existing implementation of Prim's algorithm to keep track of distances from a source. As prim and Dijkstra algorithms are almost the same. I cannot figure out where I am missing something.

I know what the problem is, but I can't figure it out.

Here is my code on how to modify it to print the shortest distance from the source to all other vertices. The minimum distance is stored in an array named: dist []

code:

package Graphs;

import java.util.ArrayList;

public class Prims {

    static int no_of_vertices = 0;

    public static void main(String[] args) {
        int[][] graph = {{0, 2, 0, 6, 0},
                {2, 0, 3, 8, 5},
                {0, 3, 0, 0, 7},
                {6, 8, 0, 0, 9},
                {0, 5, 7, 9, 0},
               };
        no_of_vertices = graph.length;
        int [][] result =  new int [no_of_vertices][no_of_vertices];
        boolean[] visited = new boolean[no_of_vertices];
        int dist[] = new int[no_of_vertices];
        for (int i = 0; i < no_of_vertices; i++)
            for (int j = 0; j < no_of_vertices; j++) {
                result[i][j]= 0;
                if (graph[i][j] == 0) {
                    graph[i][j] = Integer.MAX_VALUE;
                }
            }

        for (int i = 0; i < no_of_vertices; i++) {
            visited[i] = false;
            dist[i] = 0;

        }
        ArrayList<String> arr = new ArrayList<String>();
        int min;
        visited[0] = true;
        int counter = 0;
        while (counter < no_of_vertices - 1) {
            min = 999;
            for (int i = 0; i < no_of_vertices; i++) {
                if (visited[i] == true) {
                    for (int j = 0; j < no_of_vertices; j++) {
                        if (!visited[j] && min > graph[i][j]) {
                            min = graph[i][j];
                            dist[i] += min; //  <------ Problem here
                            visited[j] = true;
                            arr.add("Src :" + i + " Destination : " + j
                                    + " Weight : " + min);
                        }
                    }
                }
            }
            counter++;
        }


        for (int i = 0; i < no_of_vertices; i++) {
            System.out.println("Source :  0" + " Destination : " + i
                    + " distance : " + dist[i]);
        }

        for (String str : arr) {
            System.out.println(str);
        }
    }
}

      

An error occurs when calculating the distance array because it forgets to add the distance between any intermediate nodes from the source to the destination.

+3


source to share


1 answer


for (int j = 0; j < no_of_vertices; j++) {
    if (!visited[j] && min > graph[i][j]) {
        min = graph[i][j];
        dist[i] += min; //  <------ Problem here

      

Of course no intermediate edges are added because you are only adding the current edge. You probably want something like:

if (dist[i] + graph[i][j] < dist[j])
    dist[j] = dist[i] + graph[i][j];

      



And get rid of the variable min

.

Though your algorithm doesn't look correct to me. You have to select the node with the minimum d[]

at each step and update that node is neighbors as I wrote above, then mark it as selected and never select it again.

+2


source







All Articles