FilesExpand file tree

 main

/

DijkstrasAlgorithm.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

84 lines (65 loc) · 2.04 KB

 main

/

DijkstrasAlgorithm.java

Copy path

Top

File metadata and controls

• Code
• Blame

84 lines (65 loc) · 2.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import java.util.*;

class Node implements Comparator<Node>

{

private int v;

private int weight;

Node(int _v, int _w) { v = _v; weight = _w; }

Node() {}

int getV() { return v; }

int getWeight() { return weight; }

@Override

public int compare(Node node1, Node node2)

{

if (node1.weight < node2.weight)

return -1;

if (node1.weight > node2.weight)

return 1;

return 0;

}

}

class Main

{

void shortestPath(int s, ArrayList<ArrayList<Node>> adj, int N)

{

int dist[] = new int[N];

for(int i = 0;i<N;i++) dist[i] = 100000000;

dist[s] = 0;

PriorityQueue<Node> pq = new PriorityQueue<Node>(N, new Node());

pq.add(new Node(s, 0));

while(pq.size() > 0) {

Node node = pq.poll();

for(Node it: adj.get(node.getV())) {

if(dist[node.getV()] + it.getWeight() < dist[it.getV()]) {

dist[it.getV()] = dist[node.getV()] + it.getWeight();

pq.add(new Node(it.getV(), dist[it.getV()]));

}

}

}

System.out.println("The distances from source "+s+" are : ");

for (int i = 0; i < N; i++)

{

System.out.print( dist[i] + " ");

}

}

public static void main(String args[])

{

int n = 5;

ArrayList<ArrayList<Node> > adj = new ArrayList<ArrayList<Node> >();

for (int i = 0; i < n; i++)

adj.add(new ArrayList<Node>());

adj.get(0).add(new Node(1, 2));

adj.get(1).add(new Node(0, 2));

adj.get(1).add(new Node(2, 4));

adj.get(2).add(new Node(1, 4));

adj.get(0).add(new Node(3, 1));

adj.get(3).add(new Node(0, 1));

adj.get(3).add(new Node(2, 3));

adj.get(2).add(new Node(3, 3));

adj.get(1).add(new Node(4, 5));

adj.get(4).add(new Node(1, 5));

adj.get(2).add(new Node(4, 1));

adj.get(4).add(new Node(2, 1));

Main obj = new Main();

obj.shortestPath(0, adj, n);

}

}