Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Minimum distance for source vertex 0 to reach vertex 0 is 0
- Minimum distance for source vertex 0 to reach vertex 1 is 4
- Minimum distance for source vertex 0 to reach vertex 2 is 12
- Minimum distance for source vertex 0 to reach vertex 3 is 19
- Minimum distance for source vertex 0 to reach vertex 4 is 21
- Minimum distance for source vertex 0 to reach vertex 5 is 11
- Minimum distance for source vertex 0 to reach vertex 6 is 9
- Minimum distance for source vertex 0 to reach vertex 7 is 8
- Minimum distance for source vertex 0 to reach vertex 8 is 14
- Minimum distance for source vertex 0 to reach vertex 0 is 0
- Minimum distance for source vertex 0 to reach vertex 1 is 4
- Minimum distance for source vertex 0 to reach vertex 2 is 2
- Minimum distance for source vertex 0 to reach vertex 3 is 7
- Minimum distance for source vertex 0 to reach vertex 4 is 9
- Minimum distance for source vertex 0 to reach vertex 5 is 2
- Minimum distance for source vertex 0 to reach vertex 6 is 1
- Minimum distance for source vertex 0 to reach vertex 7 is 1
- Minimum distance for source vertex 0 to reach vertex 8 is 2
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
- import java.util.PriorityQueue;
- import java.util.Queue;
- public class Dijkstra
- {
- public static final int INF = 100000;
- private static class IPair implements Comparable<IPair>
- {
- int first;
- int second;
- IPair(int first, int second)
- {
- this.first = first;
- this.second = second;
- }
- public int compareTo(IPair that)
- {
- return this.first - that.first;
- }
- }
- public static int[] dijkstra(List<IPair>[] adj, int source)
- {
- Queue<IPair> pq = new PriorityQueue<>();
- int[] dist = new int[adj.length];
- boolean[] visited = new boolean[adj.length];
- Arrays.fill(dist, INF);
- pq.add(new IPair(0, source));
- dist[source] = 0;
- while (!pq.isEmpty())
- {
- int u = pq.poll().second;
- if (visited[u])
- continue;
- System.err.println(u);
- visited[u] = true;
- for (IPair pair : adj[u])
- {
- int v = pair.first;
- int weight = pair.second;
- if (dist[v] > dist[u] + weight)
- {
- dist[v] = dist[u] + weight;
- pq.add(new IPair(dist[v], v));
- System.err.println(Arrays.toString(dist));
- }
- }
- }
- return dist;
- }
- private static void addEdge(List<IPair>[] adj, int u, int v, int weight)
- {
- adj[u].add(new IPair(v, weight));
- adj[v].add(new IPair(u, weight));
- }
- public static void main(String[] args)
- {
- int V = 9;
- List<IPair>[] adj = new ArrayList[V];
- Arrays.fill(adj, new ArrayList<IPair>());
- addEdge(adj, 0, 1, 4);
- addEdge(adj, 0, 7, 8);
- addEdge(adj, 1, 2, 8);
- addEdge(adj, 1, 7, 11);
- addEdge(adj, 2, 3, 7);
- addEdge(adj, 2, 8, 2);
- addEdge(adj, 2, 5, 4);
- addEdge(adj, 3, 4, 9);
- addEdge(adj, 3, 5, 14);
- addEdge(adj, 4, 5, 10);
- addEdge(adj, 5, 6, 2);
- addEdge(adj, 6, 7, 1);
- addEdge(adj, 6, 8, 6);
- addEdge(adj, 7, 8, 7);
- int[] dist = dijkstra(adj, 0);
- for (int i = 0; i < V; ++i)
- System.out.println("Minimum distance for source vertex " + 0 + " to reach vertex " + i + " is " + dist[i]);
- }
- }
Add Comment
Please, Sign In to add comment