dijkstra algorithm using adjacency list java

1#include<iostream>
2#include<set>
3#include<list>
4#include<algorithm>
5using namespace std;
6
7typedef struct nodes {
8   int dest;
9   int cost;
10}node;
11
12class Graph {
13   int n;
14   list<node> *adjList;
15   private:
16      void showList(int src, list<node> lt) {
17         list<node> :: iterator i;
18         node tempNode;
19
20         for(i = lt.begin(); i != lt.end(); i++) {
21            tempNode = *i;
22            cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
23         }
24         cout << endl;
25      }
26   public:
27      Graph() {
28         n = 0;
29      }
30
31      Graph(int nodeCount) {
32         n = nodeCount;
33         adjList = new list<node>[n];
34      }
35
36      void addEdge(int source, int dest, int cost) {
37         node newNode;
38         newNode.dest = dest;
39         newNode.cost = cost;
40         adjList[source].push_back(newNode);
41      }
42
43      void displayEdges() {
44         for(int i = 0; i<n; i++) {
45            list<node> tempList = adjList[i];
46            showList(i, tempList);
47         }
48      }
49
50      friend void dijkstra(Graph g, int *dist, int *prev, int start);
51};
52
53void dijkstra(Graph g, int *dist, int *prev, int start) {
54   int n = g.n;
55
56   for(int u = 0; u<n; u++) {
57      dist[u] = 9999;   //set as infinity
58      prev[u] = -1;    //undefined previous
59   }
60
61   dist[start] = 0;   //distance of start is 0
62   set<int> S;       //create empty set S
63   list<int> Q;
64
65   for(int u = 0; u<n; u++) {
66      Q.push_back(u);    //add each node into queue
67   }
68
69   while(!Q.empty()) {
70      list<int> :: iterator i;
71      i = min_element(Q.begin(), Q.end());
72      int u = *i; //the minimum element from queue
73      Q.remove(u);
74      S.insert(u); //add u in the set
75      list<node> :: iterator it;
76
77      for(it = g.adjList[u].begin(); it != g.adjList[u].end();it++) {
78         if((dist[u]+(it->cost)) < dist[it->dest]) { //relax (u,v)
79            dist[it->dest] = (dist[u]+(it->cost));
80            prev[it->dest] = u;
81         }
82      }
83   }
84}
85
86main() {
87   int n = 7;
88   Graph g(n);
89   int dist[n], prev[n];
90   int start = 0;
91
92   g.addEdge(0, 1, 3);
93   g.addEdge(0, 2, 6);
94   g.addEdge(1, 0, 3);
95   g.addEdge(1, 2, 2);
96   g.addEdge(1, 3, 1);
97   g.addEdge(2, 1, 6);
98   g.addEdge(2, 1, 2);
99   g.addEdge(2, 3, 1);
100   g.addEdge(2, 4, 4);
101
102   g.addEdge(2, 5, 2);
103   g.addEdge(3, 1, 1);
104   g.addEdge(3, 2, 1);
105   g.addEdge(3, 4, 2);
106   g.addEdge(3, 6, 4);
107   g.addEdge(4, 2, 4);
108   g.addEdge(4, 3, 2);
109   g.addEdge(4, 5, 2);
110   g.addEdge(4, 6, 1);
111   g.addEdge(5, 2, 2);
112   g.addEdge(5, 4, 2);
113   g.addEdge(5, 6, 1);
114   g.addEdge(6, 3, 4);
115   g.addEdge(6, 4, 1);
116   g.addEdge(6, 5, 1);
117
118   dijkstra(g, dist, prev, start);
119
120   for(int i = 0; i<n; i++)
121      if(i != start)
122         cout<<start<<" to "<<i<<", Cost: "<<dist[i]<<" Previous: "<<prev[i]<<endl;
123}