Dijkstra.java

Dijkstra.java

/*
Algoritmul lui Dijkstra (Tehnica GREEDY):

Structuri de date:

V[x] = lista vecinilor (liste de adiacenta)

C[x] = costurile catre acei vecinilor

distMin[i] = distanta minima cunoscuta de la nodul 1 la nodul i
distMin[3] = distanta minima cunoscuta de la nodul 1 la nodul 3

Queue = coada FIFO cu nodurile de procesat

inQueue[i] = marcheaza daca nodul i este deja in coada (evitam duplicatele)

Pasi:

1. initializare: toate distantele = infinit, exceptie distMin[1] = 0;

Putem nodul 1 in COADA

2. Atata timp cand coada nu este goala:

- scoatem un nod CURR din coada;

- pentru fiecare vecin y al lui CURR cu cost Cost:

  -- daca distMin[curr] + cost < distMin[y] (adica am gasit o cale mai scurta catre y prin curr) -> actualizam distMin[y] (relaxare)

  -- daca y nu este deja in coada, il adaugam (ca sa-i propagam mai departe imbunantatirea catre proprii vecini)

  3. Rezultatul: distMin[i] contine distanta minima de la 1 la i sau ramane infinit nodul este inaccesibil, cazul in care afiseaza 0)_
*/

import java.io.*;
import java.util.*;

public class Dijkstra {

        static final int MAXN = 50005;
        static final int PlusInfinity = (1 << 31) - 1;

        static List<List<Integer>> V = new ArrayList<>(MAXN);
        static List<List<Integer>> C = new ArrayList<>(MAXN);

        static Queue<Integer> queue = new LinkedList<>();
        static int[] distMin = new int[MAXN];
        static boolean[] inQueue = new boolean[MAXN];

        static int nodes, edges;

        static final String FIN = "dijkstra.in";
        static final String FOUT = "dijkstra.out";

        public static void main(String[] args) throws IOException {

               //initializam listele de adiacenta (in c++: vector<int> V[MAXN])
              for(int i = 0; i < MAXN; ++i) {
                
                  V.add(new ArrayList<>());
                  
                  C.add(new ArrayList<>());
              }


              ReadGraph();

              displayGraph();
              displayCosts();

              dijkstra();

              WriteData();
        }

/*
1 2 1
1 4 2
1 6 3
1 7 11

1: 2, 4, 6, 7
*/

        //Tehnica Greedy

        static void dijkstra() {

                 //distanta de la nodul 1 la fiecare nod va fi +oo;
                 for(int i = 2; i <= nodes; ++i) distMin[i] = PlusInfinity;

                 //distanta de la nodul 1 la nodul 1 => 0
                 distMin[ 1 ] = 0;

                 //adaug nodul 1 in coada
                 queue.add( 1 );

                 //marchez faptul ca nodul 1 se afla in coada
                 inQueue[ 1 ] = true;

                 //atata timp cat avem noduri in coada se executa instructiunile
                 while(!queue.isEmpty()) {

                       //luam nodul din fata cozii
                       int curr = queue.poll();

                       //marcam faptul ca nodul curr nu mai figureaza in COADA
                       inQueue[ curr ] = false;

                       //iteram prin toti descendentii nodului curr
                       for(int i = 0; i < V.get(curr).size(); ++i) {

                               int y = V.get(curr).get(i);

                               int cost = C.get(curr).get(i);

                               //daca distanta gasita este buna, actualizam

                               if( distMin[y] > distMin[curr] + cost ) {

                                    distMin[ y ] = distMin[curr] + cost;

                                    //daca nu se afla in coada , il adaugam
                                    if(!inQueue[y]) {

                                        queue.add( y );

                                        inQueue[y] = true; //marcam faptul ca y este in coada
                                    }
                               }
                       }

                 }
        }


        static void ReadGraph() throws IOException {

              BufferedReader br = new BufferedReader(new FileReader(FIN));

              StreamTokenizer st = new StreamTokenizer( br );

              st.nextToken();

              nodes = (int) st.nval;

              st.nextToken();

              edges = (int) st.nval;

              for(int edge = 1; edge <= edges; ++edge) {

                   st.nextToken();

                   int x = (int) st.nval;

                   st.nextToken();

                   int y = (int) st.nval;

                   st.nextToken();

                   int cost = (int) st.nval;

                   V.get( x ).add(y);
                   C.get( x ).add(cost);
              }

              br.close();

        }

        static void displayCosts() {


          System.out.println("Graful Costurilor: ");

          for(int i = 1; i <= nodes; ++i ){

              System.out.print("Node: " + i + " ---> ");

              for(int j = 0; j < V.get(i).size(); j++) {

                   System.out.print(C.get(i).get(j) + " ");
              }

              System.out.println();
          }
        }

        static void displayGraph() {

             System.out.println("Graful reprezentat prin liste de adiacenta: ");

             for(int i = 1; i <= nodes; ++i ){

                 System.out.print("Node: " + i + " ---> ");

                 for(int j = 0; j < V.get(i).size(); j++) {

                      System.out.print(V.get(i).get(j) + " ");
                 }

                 System.out.println();
             }
        }


        static void WriteData() throws IOException {

            PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(FOUT)))  ;

            StringBuilder sb = new StringBuilder();

            for(int i  = 2; i <= nodes; ++i) {

                sb.append(distMin[i] < PlusInfinity ? distMin[ i ] : 0).append(" ");
            }

            pw.print(sb.toString());

            pw.close();
        }

}