Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
jgrapht/ShortestPath.java
import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.graph.WeightedMultigraph;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm.SingleSourcePaths;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
public class ShortestPath {
public static void main( String args[] ) {
// グラフオブジェクトを作成
Graph<Station,Line> graph = new WeightedMultigraph<>(Line.class);
// 頂点となる駅
Station shibuya = new Station( "渋谷" ); // 渋谷
Station shinjuku = new Station( "新宿" ); // 新宿
Station kichijoji = new Station( "吉祥寺" ); // 吉祥寺
Station tachikawa = new Station( "立川" ); // 立川
// 辺となる路線
Line chuo_shinjuku_tachikawa = new Line( "中央線", 36);
Line chuo_shinjuku_kichijoji = new Line( "中央線", 12 );
Line chuo_kichijoji_tachikawa = new Line( "中央線", 27 );
Line yamanote_shibuya_shinjuku = new Line( "山手線", 7 );
Line keio_shibuya_kichijoji = new Line( "京王井の頭線", 17 );
// 頂点を追加
graph.addVertex( shibuya );
graph.addVertex( shinjuku );
graph.addVertex( kichijoji );
graph.addVertex( tachikawa );
// 辺を追加
graph.addEdge( shinjuku, tachikawa, chuo_shinjuku_tachikawa );
graph.addEdge( shinjuku, kichijoji, chuo_shinjuku_kichijoji );
graph.addEdge( kichijoji, tachikawa, chuo_kichijoji_tachikawa );
graph.addEdge( shibuya, shinjuku, yamanote_shibuya_shinjuku );
graph.addEdge( shibuya, kichijoji, keio_shibuya_kichijoji );
// 辺の重みを追加
graph.setEdgeWeight( chuo_shinjuku_tachikawa, chuo_shinjuku_tachikawa.getTime() );
graph.setEdgeWeight( chuo_shinjuku_kichijoji, chuo_shinjuku_kichijoji.getTime() );
graph.setEdgeWeight( chuo_kichijoji_tachikawa, chuo_kichijoji_tachikawa.getTime() );
graph.setEdgeWeight( yamanote_shibuya_shinjuku, yamanote_shibuya_shinjuku.getTime() );
graph.setEdgeWeight( keio_shibuya_kichijoji, keio_shibuya_kichijoji.getTime() );
// 最短路問題を解く (渋谷からすべての駅までの最短路を求める)
DijkstraShortestPath<Station,Line> dijkstra = new DijkstraShortestPath<>( graph );
SingleSourcePaths<Station,Line> paths = dijkstra.getPaths( shibuya );
// 立川までの最短路を取得する
GraphPath<Station,Line> path = paths.getPath( tachikawa );
// 最短路の長さ (重みの総和) を取得する
System.out.println( "所要時間: " + path.getWeight() + "" );
System.out.println( "" );
// 最短路上の頂点を取得する
System.out.println( "経路:" );
for ( Station station : path.getVertexList() ) {
System.out.println( station.getName() );
}
System.out.println( "" );
// 最短路上の辺を取得する
System.out.println( "各区間での所要時間:" );
for ( Line line : path.getEdgeList() ) {
System.out.println( line.getName() + ": " + line.getTime() + "" );
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.