Here we created a maven project, then use JGraphT library to solve the Dijkstra's shortest path problem.
java code
package com.mycompany.app;
import java.net.*;
import org.jgrapht.*;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.*;
/**
* A simple introduction to using JGraphT.
*
* @author Barak Naveh
* @since Jul 27, 2003
*/
public final class HelloJGraphT
{
private HelloJGraphT()
{
} // ensure non-instantiability.
/**
* The starting point for the demo.
*
* @param args ignored.
*/
public static void main(String[] args)
{
Graph<String, DefaultEdge> stringGraph = createStringGraph();
// note undirected edges are printed as: {<v1>,<v2>}
System.out.println(stringGraph.toString());
// create a graph based on URL objects
Graph<URL, DefaultEdge> hrefGraph = createHrefGraph();
// note directed edges are printed as: (<v1>,<v2>)
System.out.println(hrefGraph.toString());
DefaultDirectedGraph<String, DefaultEdge> dg = createDiGraph();
DijkstraShortestPath<String, DefaultEdge> dp = new DijkstraShortestPath<>(dg);
dp.getPath("v1", "v4").getEdgeList().stream().forEach(System.out::println);
}
/**
* Creates a toy directed graph based on URL objects that represents link structure.
*
* @return a graph based on URL objects.
*/
private static Graph<URL, DefaultEdge> createHrefGraph()
{
Graph<URL, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);
try {
URL amazon = new URL("http://www.amazon.com");
URL yahoo = new URL("http://www.yahoo.com");
URL ebay = new URL("http://www.ebay.com");
// add the vertices
g.addVertex(amazon);
g.addVertex(yahoo);
g.addVertex(ebay);
// add edges to create linking structure
g.addEdge(yahoo, amazon);
g.addEdge(yahoo, ebay);
} catch (MalformedURLException e) {
e.printStackTrace();
}
return g;
}
/**
* Create a toy graph based on String objects.
*
* @return a graph based on String objects.
*/
private static Graph<String, DefaultEdge> createStringGraph()
{
Graph<String, DefaultEdge> g = new SimpleGraph<>(DefaultEdge.class);
String v1 = "v1";
String v2 = "v2";
String v3 = "v3";
String v4 = "v4";
// add the vertices
g.addVertex(v1);
g.addVertex(v2);
g.addVertex(v3);
g.addVertex(v4);
// add edges to create a circuit
g.addEdge(v1, v2);
g.addEdge(v2, v3);
g.addEdge(v3, v4);
g.addEdge(v4, v1);
return g;
}
private static DefaultDirectedGraph<String, DefaultEdge> createDiGraph()
{
DefaultDirectedGraph<String, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);
String v1 = "v1";
String v2 = "v2";
String v3 = "v3";
String v4 = "v4";
// add the vertices
g.addVertex(v1);
g.addVertex(v2);
g.addVertex(v3);
g.addVertex(v4);
// add edges to create a circuit
g.addEdge(v1, v2);
g.addEdge(v2, v3);
g.addEdge(v3, v4);
g.addEdge(v4, v1);
g.addEdge(v2, v4);
return g;
}
}
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>com.mycompany.app</groupId>
<artifactId>my-app</artifactId>
<packaging>jar</packaging>
<version>1.0-SNAPSHOT</version>
<name>my-app</name>
<url>http://maven.apache.org</url>
<dependencies>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>3.8.1</version>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.1.0</version>
</dependency>
</dependencies>
</project>
Demo>cat ~/.bashrc | grep PATH
export PATH=/Users/homenetwork/Downloads/apache-maven-3.2.5/bin/:$PATH
export PATH=/opt/local/bin:$PATH
mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DinteractiveMode=false
cd my-app
man clean package
