jgrapht/ShortestPath.java

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() + "分" );
        }
    }
}