Skip to content

Commit d33c84f

Browse files
yanglbmeyanglbme
authored
Merge pull request TheAlgorithms#558 from rmakynen/master
Added an explanation to SkylineProblem
2 parents 1b89f03 + efae9fb commit d33c84f

File tree

2 files changed

+177
-0
lines changed

2 files changed

+177
-0
lines changed

‎Others/Dijkstra.java

Lines changed: 171 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,171 @@
1+
package Others;
2+
3+
4+
/**
5+
* Dijkstra's algorithm,is a graph search algorithm that solves the single-source
6+
* shortest path problem for a graph with nonnegative edge path costs, producing
7+
* a shortest path tree.
8+
*
9+
* NOTE: The inputs to Dijkstra's algorithm are a directed and weighted graph consisting
10+
* of 2 or more nodes, generally represented by an adjacency matrix or list, and a start node.
11+
*
12+
* Original source of code: https://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java
13+
* Also most of the comments are from RosettaCode.
14+
*
15+
*/
16+
//import java.io.*;
17+
import java.util.*;
18+
public class Dijkstra {
19+
private static final Graph.Edge[] GRAPH = {
20+
new Graph.Edge("a", "b", 7), //Distance from node "a" to node "b" is 7. In the current Graph there is no way to move the other way (e,g, from "b" to "a"), a new edge would be needed for that
21+
new Graph.Edge("a", "c", 9),
22+
new Graph.Edge("a", "f", 14),
23+
new Graph.Edge("b", "c", 10),
24+
new Graph.Edge("b", "d", 15),
25+
new Graph.Edge("c", "d", 11),
26+
new Graph.Edge("c", "f", 2),
27+
new Graph.Edge("d", "e", 6),
28+
new Graph.Edge("e", "f", 9),
29+
};
30+
private static final String START = "a";
31+
private static final String END = "e";
32+
33+
/**
34+
* main function
35+
* Will run the code with "GRAPH" that was defined above.
36+
*/
37+
public static void main(String[] args) {
38+
Graph g = new Graph(GRAPH);
39+
g.dijkstra(START);
40+
g.printPath(END);
41+
//g.printAllPaths();
42+
}
43+
}
44+
45+
class Graph {
46+
private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges
47+
48+
/** One edge of the graph (only used by Graph constructor) */
49+
public static class Edge {
50+
public final String v1, v2;
51+
public final int dist;
52+
public Edge(String v1, String v2, int dist) {
53+
this.v1 = v1;
54+
this.v2 = v2;
55+
this.dist = dist;
56+
}
57+
}
58+
59+
/** One vertex of the graph, complete with mappings to neighbouring vertices */
60+
public static class Vertex implements Comparable<Vertex> {
61+
public final String name;
62+
public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
63+
public Vertex previous = null;
64+
public final Map<Vertex, Integer> neighbours = new HashMap<>();
65+
66+
public Vertex(String name) {
67+
this.name = name;
68+
}
69+
70+
private void printPath() {
71+
if (this == this.previous) {
72+
System.out.printf("%s", this.name);
73+
}
74+
else if (this.previous == null) {
75+
System.out.printf("%s(unreached)", this.name);
76+
}
77+
else {
78+
this.previous.printPath();
79+
System.out.printf(" -> %s(%d)", this.name, this.dist);
80+
}
81+
}
82+
83+
public int compareTo(Vertex other) {
84+
if (dist == other.dist)
85+
return name.compareTo(other.name);
86+
87+
return Integer.compare(dist, other.dist);
88+
}
89+
90+
@Override public String toString() {
91+
return "(" + name + ", " + dist + ")";
92+
}
93+
}
94+
95+
/** Builds a graph from a set of edges */
96+
public Graph(Edge[] edges) {
97+
graph = new HashMap<>(edges.length);
98+
99+
//one pass to find all vertices
100+
for (Edge e : edges) {
101+
if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
102+
if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
103+
}
104+
105+
//another pass to set neighbouring vertices
106+
for (Edge e : edges) {
107+
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
108+
//graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
109+
}
110+
}
111+
112+
/** Runs dijkstra using a specified source vertex */
113+
public void dijkstra(String startName) {
114+
if (!graph.containsKey(startName)) {
115+
System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
116+
return;
117+
}
118+
final Vertex source = graph.get(startName);
119+
NavigableSet<Vertex> q = new TreeSet<>();
120+
121+
// set-up vertices
122+
for (Vertex v : graph.values()) {
123+
v.previous = v == source ? source : null;
124+
v.dist = v == source ? 0 : Integer.MAX_VALUE;
125+
q.add(v);
126+
}
127+
128+
dijkstra(q);
129+
}
130+
131+
/** Implementation of dijkstra's algorithm using a binary heap. */
132+
private void dijkstra(final NavigableSet<Vertex> q) {
133+
Vertex u, v;
134+
while (!q.isEmpty()) {
135+
136+
u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
137+
if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable
138+
139+
//look at distances to each neighbour
140+
for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
141+
v = a.getKey(); //the neighbour in this iteration
142+
143+
final int alternateDist = u.dist + a.getValue();
144+
if (alternateDist < v.dist) { // shorter path to neighbour found
145+
q.remove(v);
146+
v.dist = alternateDist;
147+
v.previous = u;
148+
q.add(v);
149+
}
150+
}
151+
}
152+
}
153+
154+
/** Prints a path from the source to the specified vertex */
155+
public void printPath(String endName) {
156+
if (!graph.containsKey(endName)) {
157+
System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
158+
return;
159+
}
160+
161+
graph.get(endName).printPath();
162+
System.out.println();
163+
}
164+
/** Prints the path from the source to every vertex (output order is not guaranteed) */
165+
public void printAllPaths() {
166+
for (Vertex v : graph.values()) {
167+
v.printPath();
168+
System.out.println();
169+
}
170+
}
171+
}

‎SkylineProblem/SkylineProblem.java

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,9 @@
1+
/**
2+
* Given n rectangular buildings in a 2-dimensional city, computes the skyline of these buildings,
3+
* eliminating hidden lines. The main task is to view buildings from a side and remove all sections
4+
* that are not visible.
5+
* Source for explanation: https://www.geeksforgeeks.org/the-skyline-problem-using-divide-and-conquer-algorithm/
6+
*/
17
import java.util.ArrayList;
28
import java.util.Iterator;
39
import java.util.Scanner;

0 commit comments

Comments
 (0)