algorithm-practice/Dijikstra.java at main · tushar-gupta-1995/algorithm-practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package MyPractice;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.stream.IntStream;

public class Dijikstra {

    public static class Node {
        int src;
        int dst;
        int distance;
    }

    static HashMap<Integer, List<Node>> adjList = new HashMap<Integer, List<Node>>();
    static boolean [] processed = new boolean[201];

    static int [] distance = new int [201];

    public static void initDistance() {
        for (int i=0;i< distance.length;i++)
        {
            distance[i]=1000000;
        }
    }

    public static void main(String...args) {
        readFromFile();
        initDistance();

        runDijikstra(0);

        //7,37,59,82,99,115,133,165,188,197
        System.out.print(distance[6]+",");
        System.out.print(distance[36]+",");
        System.out.print(distance[58]+",");
        System.out.print(distance[81]+",");
        System.out.print(distance[98]+",");
        System.out.print(distance[114]+",");
        System.out.print(distance[132]+",");
        System.out.print(distance[164]+",");
        System.out.print(distance[187]+",");
        System.out.print(distance[196]+",");

    }

    public static void runDijikstra(int srcNode) {
        LinkedList<Integer> connectedNodes = new LinkedList<>();
        connectedNodes.add(srcNode);
        int minVertex = srcNode;
        distance[srcNode]=0;
        while (connectedNodes.size()>0) {
            //System.out.println("vert" + minVertex);
            if(minVertex==-1)
                break;
            List<Node> nodeList = adjList.get(minVertex);
            for (int i = 0; i < nodeList.size(); i++) {
                Node n = nodeList.get(i);
                connectedNodes.add(n.dst);
                int mindst = Math.min(distance[n.dst], distance[n.src] + n.distance);
               // System.out.println("Min distance between " + n.dst + " and " + n.src + " is " + mindst);
                distance[n.dst]=mindst;
            }
            processed[minVertex]=true;
            connectedNodes.remove(new Integer(minVertex));
            minVertex = getVertexWithMinDist(connectedNodes);
        }


    }

    public static int getVertexWithMinDist(LinkedList<Integer> nodes)
    {

        int vertexToReturn=0;

        int min=100000;

        for(int i=0;i< nodes.size();i++)
        {
            int vertex = nodes.get(i);
            if(processed[vertex]==false && distance[vertex]<min)
            {
                min=distance[vertex];
                vertexToReturn=vertex;
            }

        }

        if(processed[vertexToReturn]==true)
            return -1;
        return vertexToReturn;
    }

    public static void readFromFile() {
        try {
            BufferedReader reader = new BufferedReader(new FileReader("C:\\Users\\gupta\\IdeaProjects\\untitled\\src\\MyPractice\\dijikstra.txt"));
            String line = reader.readLine();
           // line = line.replaceAll("\s+","t");

            while (line != null) {
                // System.out.println(line);
                String [] values = line.split("\t");
               // System.out.println(values[0]);
                int src = Integer.parseInt(values[0])-1;

                List<Node> nodeList = new ArrayList<>();
                for(int i=1;i<values.length;i++)
                {
                    String [] dstDestination = values[i].split(",");
                    int dst = Integer.parseInt(dstDestination[0])-1;
                    int distance = Integer.parseInt(dstDestination[1]);
                    Node n = new Node();
                    n.src=src;
                    n.dst=dst;
                    n.distance=distance;
                    nodeList.add(n);
                }
                adjList.put(src,nodeList);
                // read next line
                line = reader.readLine();
            }

            reader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}