jgrapht

Line.java

public class Line {
    private final String name;
    private final int price;
    private final int time;

    Line( String name, int price, int time ) {
        this.name = name;
        this.price = price;
        this.time = time;
    }

    public String getName() {
        return this.name;
    }
    public int getPrice() {
        return this.price;
    }
    public int getTime() {
        return this.time;
    }

    @Override
    public String toString() {
        return "Line [name=" + name + ", price=" + price + ", time=" + time + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + price;
        result = prime * result + time;
        return result;
    }

    @Override
    public boolean equals( Object obj ) {
        if ( this == obj ) return true;
        if ( obj == null ) return false;
        if ( getClass() != obj.getClass() ) return false;
        Line other = (Line)obj;
        if ( name == null ) {
            if ( other.name != null ) return false;
        } else if ( ! name.equals( other.name ) ) {
            return false;
        }
        if ( price != other.price ) {
            return false;
        }
        if ( time != other.time ) {
            return false;
        }
        return true;
    }
}

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( "Shibuya" );     // 渋谷
        Station shinjuku = new Station( "Shinjuku" );   // 新宿
        Station kichijoji = new Station( "Kichijoji" ); // 吉祥寺
        Station tachikawa = new Station( "Tachikawa" ); // 立川

        // 辺となる路線
        Line chuo_shinjuku_tachikawa = new Line( "Chuo", 464, 36);
        Line chuo_shinjuku_kichijoji = new Line( "Chuo", 216, 12 );
        Line chuo_kichijoji_tachikawa = new Line( "Chuo", 216, 27 );
        Line yamanote_shibuya_shinjuku = new Line( "Yamanote", 154, 7 );
        Line keio_shibuya_kichijoji = new Line( "Keio", 195, 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( "Total weight: " + path.getWeight() );

        // 最短路上の頂点を取得する
        System.out.println( "Stations on shortest path:" );
        for ( Station station : path.getVertexList() ) {
            System.out.println( station.getName() );
        }

        // 最短路上の辺を取得する
        System.out.println( "Prices on shortest path:" );
        for ( Line line : path.getEdgeList() ) {
            System.out.println( line.getPrice() );
        }
    }
}

Station.java

public class Station {
    private final String name;

    Station( String name ) {
        this.name = name;
    }

    public String getName() {
        return this.name;
    }

    @Override
    public String toString() {
        return "Station [name=" + name + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals( Object obj ) {
        if ( this == obj ) return true;
        if ( obj == null ) return false;
        if ( getClass() != obj.getClass() ) return false;
        Station other = (Station)obj;
        if ( name == null ) {
            if ( other.name != null ) return false;
        } else if ( ! name.equals( other.name ) ) {
            return false;
        }
        return true;
    }
}