import java.util.List;
import org.jgrapht.*;
import org.jgrapht.alg.*;
import org.jgrapht.graph.*;
public class Dijkstra 
{
    public static void main(String[] args) 
    {
        String[] rs= {"Rumah sakit primiere surabaya","RS Royal sby","RKZ","UGD darmo surabaya","UGD siloam","UGD RSU haji surabaya","UGD siti asiyah","IGD rsal","UGD 24jam RSIA","Emergency room UGD dr Sutomo","RS Mitra Keluarga","RS kendangsari merr surabaya","puskesmas kenjeran","Rumah Sakit Gigi Dan Mulut Universitas Hang Tuah","Gotong Royong Hospital","RSUD dr. Mohamad Soewandhie","Rumah Sakit Adi Husada Kapasari","Puskesmas Wonokromo","Puskesmas Jagir","Puskesmas Jemursari","Puskesmas Keputih","Rumah Sakit Islam Surabaya","Brawijaya Hospital"};
        String[] awal= {"STIE Perbanas Surabaya","STIE Urip Sumoharjo","Sekolah Tinggi Ilmu Ekonomi Indonesia","Adhi Tama Institute of Technology","Politeknik NSC Surabaya","SMP Negeri 19 Surabaya","Sate Taichan Goreng Surabaya","GEDUNG WANITA Candra Kencana","Balai Pemuda Surabaya","Graha Sepuluh Nopember ITS Surabaya"};
        double s,a;
        String hasil;
        Multigraph<String, DefaultWeightedEdge>  graph = new Multigraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class); 
        graph.addVertex("Rumah sakit primiere surabaya");
        graph.addVertex("RS Royal sby");
        graph.addVertex("RKZ");
        graph.addVertex("UGD darmo surabaya");
        graph.addVertex("UGD siloam");
        graph.addVertex("UGD RSU haji surabaya");
        graph.addVertex("UGD siti asiyah");
        graph.addVertex("IGD rsal");
        graph.addVertex("UGD 24jam RSIA");
        graph.addVertex("Emergency room UGD dr Sutomo");
        graph.addVertex("RS Mitra Keluarga");
        graph.addVertex("RS kendangsari merr surabaya");
        graph.addVertex("puskesmas kenjeran");
        graph.addVertex("STIE Perbanas Surabaya");
        graph.addVertex("STIE Urip Sumoharjo");
        graph.addVertex("Sekolah Tinggi Ilmu Ekonomi Indonesia");
        graph.addVertex("Adhi Tama Institute of Technology");
        graph.addVertex("Politeknik NSC Surabaya");
        graph.addVertex("SMP Negeri 19 Surabaya");
        graph.addVertex("Rumah Sakit Gigi Dan Mulut Universitas Hang Tuah");
        graph.addVertex("Sate Taichan Goreng Surabaya");
        graph.addVertex("GEDUNG WANITA Candra Kencana");
        graph.addVertex("Gotong Royong Hospital");
        graph.addVertex("RSUD dr. Mohamad Soewandhie");
        graph.addVertex("Rumah Sakit Adi Husada Kapasari");
        graph.addVertex("Puskesmas Wonokromo");
        graph.addVertex("Puskesmas Jagir");
        graph.addVertex("Puskesmas Jemursari");
        graph.addVertex("Puskesmas Keputih");
        graph.addVertex("Balai Pemuda Surabaya");
        graph.addVertex("Rumah Sakit Islam Surabaya");
        graph.addVertex("Graha Sepuluh Nopember ITS Surabaya");
        graph.addVertex("Brawijaya Hospital");
        DefaultWeightedEdge e1 = graph.addEdge("Rumah Sakit Adi Husada Kapasari", "RSUD dr. Mohamad Soewandhie"); 
        graph.setEdgeWeight(e1, 1300); 
        DefaultWeightedEdge e2 = graph.addEdge("Rumah Sakit Adi Husada Kapasari", "RS kendangsari merr surabaya"); 
        graph.setEdgeWeight(e2, 3890); 
        DefaultWeightedEdge e3 = graph.addEdge("Rumah Sakit Adi Husada Kapasari", "RS Mitra Keluarga"); 
        graph.setEdgeWeight(e3, 3910);    
        DefaultWeightedEdge e4 = graph.addEdge("RSUD dr. Mohamad Soewandhie", "RS kendangsari merr surabaya"); 
        graph.setEdgeWeight(e4, 3330);
        DefaultWeightedEdge e5 = graph.addEdge("RSUD dr. Mohamad Soewandhie", "RS Mitra Keluarga"); 
        graph.setEdgeWeight(e5, 3350); 
        DefaultWeightedEdge e6 = graph.addEdge("RSUD dr. Mohamad Soewandhie", "RS kendangsari merr surabaya"); 
        graph.setEdgeWeight(e6, 3910);
        DefaultWeightedEdge e7 = graph.addEdge("RSUD dr. Mohamad Soewandhie", "RS Mitra Keluarga"); 
        graph.setEdgeWeight(e7, 3930); 
        DefaultWeightedEdge e8 = graph.addEdge("Rumah Sakit Adi Husada Kapasari", "UGD siti asiyah"); 
        graph.setEdgeWeight(e8, 2650); 
        DefaultWeightedEdge e9 = graph.addEdge("RS kendangsari merr surabaya", "UGD siti asiyah"); 
        graph.setEdgeWeight(e9, 4260);    
        DefaultWeightedEdge e10 = graph.addEdge("RS kendangsari merr surabaya", "UGD siti asiyah"); 
        graph.setEdgeWeight(e10, 4560);
        DefaultWeightedEdge e11 = graph.addEdge("RS Mitra Keluarga", "UGD siti asiyah"); 
        graph.setEdgeWeight(e11, 4270); 
        DefaultWeightedEdge e12 = graph.addEdge("RS Mitra Keluarga", "UGD siti asiyah"); 
        graph.setEdgeWeight(e12, 4740);
        DefaultWeightedEdge e13 = graph.addEdge("UGD siti asiyah", "Emergency room UGD dr Sutomo"); 
        graph.setEdgeWeight(e13, 1320); 
        DefaultWeightedEdge e14 = graph.addEdge("RS kendangsari merr surabaya", "Emergency room UGD dr Sutomo"); 
        graph.setEdgeWeight(e14, 5240);    
        DefaultWeightedEdge e15 = graph.addEdge("RS Mitra Keluarga", "Emergency room UGD dr Sutomo"); 
        graph.setEdgeWeight(e15, 5420);
        DefaultWeightedEdge e16 = graph.addEdge("RS kendangsari merr surabaya", "Emergency room UGD dr Sutomo"); 
        graph.setEdgeWeight(e16, 4940); 
        DefaultWeightedEdge e17 = graph.addEdge("RS Mitra Keluarga", "Emergency room UGD dr Sutomo"); 
        graph.setEdgeWeight(e17, 4960);
        DefaultWeightedEdge e18 = graph.addEdge("UGD siloam", "STIE Urip Sumoharjo"); 
        graph.setEdgeWeight(e18, 621); 
        DefaultWeightedEdge e19 = graph.addEdge("Balai Pemuda Surabaya", "STIE Urip Sumoharjo"); 
        graph.setEdgeWeight(e19, 1110); 
        DefaultWeightedEdge e20 = graph.addEdge("Balai Pemuda Surabaya", "UGD siloam"); 
        graph.setEdgeWeight(e20, 1390);    
        DefaultWeightedEdge e21 = graph.addEdge("UGD siloam", "Emergency room UGD dr Sutomo"); 
        graph.setEdgeWeight(e21, 1750);
        DefaultWeightedEdge e22 = graph.addEdge("STIE Urip Sumoharjo", "RKZ"); 
        graph.setEdgeWeight(e22, 2180); 
        DefaultWeightedEdge e23 = graph.addEdge("STIE Urip Sumoharjo", "UGD darmo surabaya"); 
        graph.setEdgeWeight(e23, 1580);
        DefaultWeightedEdge e24 = graph.addEdge("RKZ", "UGD darmo surabaya"); 
        graph.setEdgeWeight(e24, 746); 
        DefaultWeightedEdge e25 = graph.addEdge("RS Mitra Keluarga", "RS kendangsari merr surabaya"); 
        graph.setEdgeWeight(e25, 195); 
        DefaultWeightedEdge e26 = graph.addEdge("puskesmas kenjeran", "RS Mitra Keluarga"); 
        graph.setEdgeWeight(e26, 2310);    
        DefaultWeightedEdge e27 = graph.addEdge("puskesmas kenjeran", "RS Mitra Keluarga"); 
        graph.setEdgeWeight(e27, 2880);
        DefaultWeightedEdge e28 = graph.addEdge("RKZ", "Rumah Sakit Islam Surabaya"); 
        graph.setEdgeWeight(e28, 2240); 
        DefaultWeightedEdge e29 = graph.addEdge("Rumah Sakit Islam Surabaya", "Puskesmas Jagir"); 
        graph.setEdgeWeight(e29, 656);
        DefaultWeightedEdge e30 = graph.addEdge("IGD rsal", "Puskesmas Jagir"); 
        graph.setEdgeWeight(e30, 334); 
        DefaultWeightedEdge e31 = graph.addEdge("Rumah Sakit Islam Surabaya", "IGD rsal"); 
        graph.setEdgeWeight(e31, 749);    
        DefaultWeightedEdge e32 = graph.addEdge("Adhi Tama Institute of Technology", "SMP Negeri 19 Surabaya"); 
        graph.setEdgeWeight(e32, 281);
        DefaultWeightedEdge e33 = graph.addEdge("SMP Negeri 19 Surabaya", "UGD RSU haji surabaya"); 
        graph.setEdgeWeight(e33, 851); 
        DefaultWeightedEdge e34 = graph.addEdge("GEDUNG WANITA Candra Kencana", "Sekolah Tinggi Ilmu Ekonomi Indonesia"); 
        graph.setEdgeWeight(e34, 569);
        DefaultWeightedEdge e35 = graph.addEdge("Sekolah Tinggi Ilmu Ekonomi Indonesia", "Adhi Tama Institute of Technology"); 
        graph.setEdgeWeight(e35, 1420); 
        DefaultWeightedEdge e36 = graph.addEdge("UGD RSU haji surabaya", "RS Mitra Keluarga"); 
        graph.setEdgeWeight(e36, 3870); 
        DefaultWeightedEdge e37 = graph.addEdge("UGD RSU haji surabaya", "RS kendangsari merr surabaya"); 
        graph.setEdgeWeight(e37, 3810);    
        DefaultWeightedEdge e38 = graph.addEdge("UGD darmo surabaya", "GEDUNG WANITA Candra Kencana"); 
        graph.setEdgeWeight(e38, 3230);
        DefaultWeightedEdge e39 = graph.addEdge("RKZ", "GEDUNG WANITA Candra Kencana"); 
        graph.setEdgeWeight(e39, 3170); 
        DefaultWeightedEdge e40 = graph.addEdge("Adhi Tama Institute of Technology", "Rumah Sakit Gigi Dan Mulut Universitas Hang Tuah"); 
        graph.setEdgeWeight(e40, 1720);
        DefaultWeightedEdge e41 = graph.addEdge("Rumah Sakit Gigi Dan Mulut Universitas Hang Tuah", "SMP Negeri 19 Surabaya"); 
        graph.setEdgeWeight(e41, 1610); 
        DefaultWeightedEdge e42 = graph.addEdge("Rumah Sakit Gigi Dan Mulut Universitas Hang Tuah", "Puskesmas Keputih"); 
        graph.setEdgeWeight(e42, 1190); 
        DefaultWeightedEdge e43 = graph.addEdge("Graha Sepuluh Nopember ITS Surabaya", "UGD RSU haji surabaya"); 
        graph.setEdgeWeight(e43, 1780);    
        DefaultWeightedEdge e44 = graph.addEdge("Puskesmas Keputih", "Graha Sepuluh Nopember ITS Surabaya"); 
        graph.setEdgeWeight(e44, 3330);
        DefaultWeightedEdge e45 = graph.addEdge("Sate Taichan Goreng Surabaya", "GEDUNG WANITA Candra Kencana"); 
        graph.setEdgeWeight(e45, 783); 
        DefaultWeightedEdge e46 = graph.addEdge("Sate Taichan Goreng Surabaya", "Sekolah Tinggi Ilmu Ekonomi Indonesia"); 
        graph.setEdgeWeight(e46, 976);
        DefaultWeightedEdge e47 = graph.addEdge("Sate Taichan Goreng Surabaya", "STIE Perbanas Surabaya"); 
        graph.setEdgeWeight(e47, 1050); 
        DefaultWeightedEdge e48 = graph.addEdge("STIE Perbanas Surabaya", "Rumah sakit primiere surabaya"); 
        graph.setEdgeWeight(e48, 1400);    
        DefaultWeightedEdge e49 = graph.addEdge("Rumah sakit primiere surabaya", "Gotong Royong Hospital"); 
        graph.setEdgeWeight(e49, 2980);
        DefaultWeightedEdge e50 = graph.addEdge("Puskesmas Jagir", "Gotong Royong Hospital"); 
        graph.setEdgeWeight(e50, 6000); 
        DefaultWeightedEdge e51 = graph.addEdge("Puskesmas Keputih", "Gotong Royong Hospital"); 
        graph.setEdgeWeight(e51, 2780);
        DefaultWeightedEdge e52 = graph.addEdge("Puskesmas Wonokromo", "Rumah Sakit Islam Surabaya"); 
        graph.setEdgeWeight(e52, 1190); 
        DefaultWeightedEdge e53 = graph.addEdge("Rumah Sakit Adi Husada Kapasari", "UGD 24jam RSIA"); 
        graph.setEdgeWeight(e53, 3280); 
        DefaultWeightedEdge e54 = graph.addEdge("Rumah sakit primiere surabaya", "Puskesmas Jemursari"); 
        graph.setEdgeWeight(e54, 4730);    
        DefaultWeightedEdge e55 = graph.addEdge("RS Royal sby", "Puskesmas Jemursari"); 
        graph.setEdgeWeight(e55, 2630);
        DefaultWeightedEdge e56 = graph.addEdge("IGD rsal", "Puskesmas Jemursari"); 
        graph.setEdgeWeight(e56, 3210); 
        DefaultWeightedEdge e57 = graph.addEdge("IGD rsal", "RS Royal sby"); 
        graph.setEdgeWeight(e57, 4430);
        DefaultWeightedEdge e58 = graph.addEdge("Rumah sakit primiere surabaya", "RS Royal sby"); 
        graph.setEdgeWeight(e58, 5520); 
        DefaultWeightedEdge e59 = graph.addEdge("RKZ", "Brawijaya Hospital"); 
        graph.setEdgeWeight(e59, 1960); 
        DefaultWeightedEdge e60 = graph.addEdge("Puskesmas Wonokromo", "Brawijaya Hospital"); 
        graph.setEdgeWeight(e60, 4070);    
        DefaultWeightedEdge e61 = graph.addEdge("RKZ", "Brawijaya Hospital"); 
        graph.setEdgeWeight(e61, 2040);
        DefaultWeightedEdge e62 = graph.addEdge("UGD siloam", "Politeknik NSC Surabaya"); 
        graph.setEdgeWeight(e62, 572); 
        DefaultWeightedEdge e63 = graph.addEdge("Balai Pemuda Surabaya", "Politeknik NSC Surabaya"); 
        graph.setEdgeWeight(e63, 823);
        DefaultWeightedEdge e64 = graph.addEdge("Balai Pemuda Surabaya", "Politeknik NSC Surabaya"); 
        graph.setEdgeWeight(e64, 1190); 
        DefaultWeightedEdge e65 = graph.addEdge("Rumah Sakit Adi Husada Kapasari", "UGD 24jam RSIA"); 
        graph.setEdgeWeight(e65, 4520);    
        DefaultWeightedEdge e66 = graph.addEdge("Rumah Sakit Adi Husada Kapasari", "Balai Pemuda Surabaya"); 
        graph.setEdgeWeight(e66, 2950);
        DefaultWeightedEdge e67 = graph.addEdge("puskesmas kenjeran", "Graha Sepuluh Nopember ITS Surabaya"); 
        graph.setEdgeWeight(e67, 4860); 
        DefaultWeightedEdge e68 = graph.addEdge("SMP Negeri 19 Surabaya", "Gotong Royong Hospital"); 
        graph.setEdgeWeight(e68, 3280);
        for(int j = 0; j<awal.length;j++)
        {
            for(int i = 0;i<rs.length;i++)
            {
                System.out.println("Shortest path from "+awal[j]+" to "+rs[i]+" :");
                List shortest_path = DijkstraShortestPath.findPathBetween(graph, awal[j], rs[i]);
                System.out.println(shortest_path);
                DijkstraShortestPath<String,DefaultWeightedEdge> fw = new DijkstraShortestPath<String,DefaultWeightedEdge>(graph, awal[j], rs[i]);
                s = fw.getPathLength();
                System.out.println("jarak terpendek : " +s);
                System.out.println("\n");
                for(int n =0;n<shortest_path.size();n++)
                {
                    hasil = shortest_path.get(n).toString();
                    String[] splits = hasil.split(":");
                    System.out.println(hasil);
                    DijkstraShortestPath<String,DefaultWeightedEdge> fw1 = new DijkstraShortestPath<String,DefaultWeightedEdge>(graph, splits[0].replace("(","").replaceFirst("\\s+$",""), splits[1].replace(")","").replaceFirst("\\s", ""));
                    a = fw1.getPathLength();
                    System.out.println("jaraknya : " +a);
                }
            }
        }   
    }   
}
