Skip to content

Commit 49c7cc8

Browse files
GuenHamzapivovarit
GuenHamza
authored and
pivovarit
committed
Add Algorithms Module (eugenp#936)
* Update pom.xml Add FindBugs reporting plugin * Add algorithms module Dijkstra implementation * Update pom.xml * Update pom.xml
1 parent 99e86c5 commit 49c7cc8

7 files changed

Lines changed: 267 additions & 14 deletions

File tree

‎algorithms/pom.xml‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
2+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
3+
<modelVersion>4.0.0</modelVersion>
4+
<groupId>com.baeldung</groupId>
5+
<artifactId>algorithms</artifactId>
6+
<version>0.0.1-SNAPSHOT</version>
7+
8+
<properties>
9+
<junit.version>4.12</junit.version>
10+
<maven-compiler-plugin.version>3.6.0</maven-compiler-plugin.version>
11+
<exec-maven-plugin.version>1.5.0</exec-maven-plugin.version>
12+
</properties>
13+
14+
<dependencies>
15+
<dependency>
16+
<groupId>junit</groupId>
17+
<artifactId>junit</artifactId>
18+
<version>${junit.version}</version>
19+
<scope>test</scope>
20+
</dependency>
21+
</dependencies>
22+
23+
<build>
24+
<defaultGoal>install</defaultGoal>
25+
<pluginManagement>
26+
<plugins>
27+
<plugin>
28+
<groupId>org.apache.maven.plugins</groupId>
29+
<artifactId>maven-compiler-plugin</artifactId>
30+
<version>${maven-compiler-plugin.version}</version>
31+
<configuration>
32+
<source>1.8</source>
33+
<target>1.8</target>
34+
</configuration>
35+
</plugin>
36+
<plugin>
37+
<groupId>org.codehaus.mojo</groupId>
38+
<artifactId>exec-maven-plugin</artifactId>
39+
<version>${exec-maven-plugin.version}</version>
40+
</plugin>
41+
</plugins>
42+
</pluginManagement>
43+
</build>
44+
</project>

‎algorithms/src/main/java/com/baeldung/algorithms/dijkstra/Dijkstra.java‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package com.baeldung.algorithms.dijkstra;
2+
3+
4+
import java.util.HashSet;
5+
import java.util.LinkedList;
6+
import java.util.Map.Entry;
7+
import java.util.Set;
8+
9+
public class Dijkstra {
10+
11+
public static Graph calculateShortestPathFromSource(Graph graph, Node source) {
12+
13+
source.setDistance(0);
14+
15+
Set<Node> settledNodes = new HashSet<Node>();
16+
Set<Node> unsettledNodes = new HashSet<Node>();
17+
unsettledNodes.add(source);
18+
19+
while (unsettledNodes.size() != 0) {
20+
Node currentNode = getLowestDistanceNode(unsettledNodes);
21+
unsettledNodes.remove(currentNode);
22+
for (Entry<Node, Integer> adjacencyPair : currentNode.getAdjacentNodes().entrySet())
23+
{
24+
Node adjacentNode = adjacencyPair.getKey();
25+
Integer edgeWeigh = adjacencyPair.getValue();
26+
27+
if (!settledNodes.contains(adjacentNode)) {
28+
CalculateMinimumDistance(adjacentNode, edgeWeigh, currentNode);
29+
unsettledNodes.add(adjacentNode);
30+
}
31+
}
32+
settledNodes.add(currentNode);
33+
}
34+
return graph;
35+
}
36+
37+
private static void CalculateMinimumDistance(Node evaluationNode, Integer edgeWeigh, Node sourceNode) {
38+
Integer sourceDistance = sourceNode.getDistance();
39+
if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) {
40+
evaluationNode.setDistance(sourceDistance + edgeWeigh);
41+
LinkedList<Node> shortestPath = new LinkedList<Node>(sourceNode.getShortestPath());
42+
shortestPath.add(sourceNode);
43+
evaluationNode.setShortestPath(shortestPath);
44+
}
45+
}
46+
47+
private static Node getLowestDistanceNode(Set<Node> unsettledNodes) {
48+
Node lowestDistanceNode = null;
49+
int lowestDistance = Integer.MAX_VALUE;
50+
for (Node node : unsettledNodes) {
51+
int nodeDistance = node.getDistance();
52+
if (nodeDistance < lowestDistance) {
53+
lowestDistance = nodeDistance;
54+
lowestDistanceNode = node;
55+
}
56+
}
57+
return lowestDistanceNode;
58+
}
59+
}

‎algorithms/src/main/java/com/baeldung/algorithms/dijkstra/Graph.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package com.baeldung.algorithms.dijkstra;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
public class Graph {
7+
8+
private Set<Node> nodes = new HashSet<Node>();
9+
10+
public void addNode(Node nodeA) {
11+
nodes.add(nodeA);
12+
}
13+
14+
public Set<Node> getNodes() {
15+
return nodes;
16+
}
17+
18+
public void setNodes(Set<Node> nodes) {
19+
this.nodes = nodes;
20+
}
21+
}

‎algorithms/src/main/java/com/baeldung/algorithms/dijkstra/Main.java‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.baeldung.algorithms.dijkstra;
2+
3+
public class Main {
4+
5+
public static void main(String[] args) {
6+
7+
8+
}
9+
}

‎algorithms/src/main/java/com/baeldung/algorithms/dijkstra/Node.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.baeldung.algorithms.dijkstra;
2+
3+
import java.util.HashMap;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
import java.util.Map;
7+
8+
public class Node {
9+
10+
private String name;
11+
12+
private LinkedList<Node> shortestPath = new LinkedList<Node>();
13+
14+
private Integer distance = Integer.MAX_VALUE;
15+
16+
Map<Node, Integer> adjacentNodes = new HashMap<Node, Integer>();
17+
18+
public Node(String name) {
19+
this.name = name;
20+
}
21+
22+
public void addDestination(Node destination, int distance) {
23+
adjacentNodes.put(destination, distance);
24+
}
25+
26+
public String getName() {
27+
return name;
28+
}
29+
30+
public void setName(String name) {
31+
this.name = name;
32+
}
33+
34+
public Map<Node, Integer> getAdjacentNodes() {
35+
return adjacentNodes;
36+
}
37+
38+
public void setAdjacentNodes(Map<Node, Integer> adjacentNodes) {
39+
this.adjacentNodes = adjacentNodes;
40+
}
41+
42+
public Integer getDistance() {
43+
return distance;
44+
}
45+
46+
public void setDistance(Integer distance) {
47+
this.distance = distance;
48+
}
49+
50+
public List<Node> getShortestPath() {
51+
return shortestPath;
52+
}
53+
54+
public void setShortestPath(LinkedList<Node> shortestPath) {
55+
this.shortestPath = shortestPath;
56+
}
57+
58+
}

‎algorithms/src/test/java/algorithms/DijkstraAlgorithmTest.java‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package algorithms;
2+
3+
import static org.junit.Assert.*;
4+
5+
import java.util.Arrays;
6+
import java.util.List;
7+
8+
import org.junit.Test;
9+
10+
import com.baeldung.algorithms.dijkstra.Dijkstra;
11+
import com.baeldung.algorithms.dijkstra.Graph;
12+
import com.baeldung.algorithms.dijkstra.Node;
13+
14+
public class DijkstraAlgorithmTest {
15+
16+
@Test
17+
public void whenSPPSolved_thenCorrect() {
18+
19+
Node nodeA = new Node("A");
20+
Node nodeB = new Node("B");
21+
Node nodeC = new Node("C");
22+
Node nodeD = new Node("D");
23+
Node nodeE = new Node("E");
24+
Node nodeF = new Node("F");
25+
26+
nodeA.addDestination(nodeB, 10);
27+
nodeA.addDestination(nodeC, 15);
28+
29+
nodeB.addDestination(nodeD, 12);
30+
nodeB.addDestination(nodeF, 15);
31+
32+
nodeC.addDestination(nodeE, 10);
33+
34+
nodeD.addDestination(nodeE, 2);
35+
nodeD.addDestination(nodeF, 1);
36+
37+
nodeF.addDestination(nodeE, 5);
38+
39+
Graph graph = new Graph();
40+
41+
graph.addNode(nodeA);
42+
graph.addNode(nodeB);
43+
graph.addNode(nodeC);
44+
graph.addNode(nodeD);
45+
graph.addNode(nodeE);
46+
graph.addNode(nodeF);
47+
48+
graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA);
49+
50+
List<Node> shortestPathForNodeB = Arrays.asList(nodeA);
51+
List<Node> shortestPathForNodeC = Arrays.asList(nodeA);
52+
List<Node> shortestPathForNodeD = Arrays.asList(nodeA, nodeB);
53+
List<Node> shortestPathForNodeE = Arrays.asList(nodeA, nodeB, nodeD);
54+
List<Node> shortestPathForNodeF = Arrays.asList(nodeA, nodeB, nodeD);
55+
56+
for(Node node : graph.getNodes()) {
57+
switch (node.getName()) {
58+
case "B":
59+
assertTrue(node.getShortestPath().equals(shortestPathForNodeB));
60+
break;
61+
case "C":
62+
assertTrue(node.getShortestPath().equals(shortestPathForNodeC));
63+
break;
64+
case "D":
65+
assertTrue(node.getShortestPath().equals(shortestPathForNodeD));
66+
break;
67+
case "E":
68+
assertTrue(node.getShortestPath().equals(shortestPathForNodeE));
69+
break;
70+
case "F":
71+
assertTrue(node.getShortestPath().equals(shortestPathForNodeF));
72+
break;
73+
}
74+
}
75+
}
76+
}

‎spring-rest/pom.xml‎

Lines changed: 0 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -357,18 +357,4 @@
357357

358358
</properties>
359359

360-
<reporting>
361-
<plugins>
362-
<plugin>
363-
<groupId>org.codehaus.mojo</groupId>
364-
<artifactId>findbugs-maven-plugin</artifactId>
365-
<version>${findbugs-maven-plugin.version}</version>
366-
<configuration>
367-
<effort>Max</effort>
368-
<omitVisitors>FindDeadLocalStores,FindNullDeref</omitVisitors>
369-
</configuration>
370-
</plugin>
371-
</plugins>
372-
</reporting>
373-
374360
</project>

0 commit comments

Comments
 (0)