Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Reitit {
- private HashMap<String, Solmu> verkko = new HashMap<>();
- public class Kaari {
- public String alku, loppu;
- int pituus;
- public Kaari(String alku, String loppu, int pituus) {
- this.alku = alku;
- this.loppu = loppu;
- this.pituus = pituus;
- }
- }
- public class Solmu implements Comparable<Solmu> {
- public final String nimi;
- public int etaisyys = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
- public Solmu edellinen = null;
- public final Map<Solmu, Integer> naapurit = new HashMap<>();
- public Solmu(String nimi) {
- this.nimi = nimi;
- }
- public int compareTo(Solmu toinen) {
- if (etaisyys == toinen.etaisyys)
- return nimi.compareTo(toinen.nimi);
- return Integer.compare(etaisyys, toinen.etaisyys);
- }
- }
- List<Kaari> kaaret = new ArrayList<>(10000);
- @SuppressWarnings("Duplicates")
- public void lisaaTie(String alku, String loppu, int pituus) {
- Kaari kaari1 = new Kaari(alku, loppu, pituus);
- Kaari kaari2 = new Kaari(loppu, alku, pituus);
- kaaret.add(kaari1);
- kaaret.add(kaari2);
- }
- public int reitinPituus(String alku, String loppu) {
- luoVerkko();
- dijkstra(alku);
- return lyhyinPolku(loppu);
- }
- private void luoVerkko() {
- verkko = new HashMap<>(kaaret.size());
- for( Kaari kaari : kaaret) {
- if( !verkko.containsKey(kaari.alku)) verkko.put(kaari.alku, new Solmu(kaari.alku));
- if( !verkko.containsKey(kaari.loppu)) verkko.put(kaari.loppu, new Solmu(kaari.loppu));
- }
- for( Kaari kaari : kaaret) {
- verkko.get(kaari.alku).naapurit.put(verkko.get(kaari.loppu), kaari.pituus);
- }
- }
- public void dijkstra(String alku) {
- if (!verkko.containsKey(alku)) {
- System.err.printf("Verkossa ei ole solmua\"%s\"\n", alku);
- return;
- }
- final Solmu source = verkko.get(alku);
- NavigableSet<Solmu> q = new TreeSet<>();
- // set-up vertices
- for (Solmu v : verkko.values()) {
- v.edellinen = v == source ? source : null;
- v.etaisyys = v == source ? 0 : Integer.MAX_VALUE;
- q.add(v);
- }
- dijkstra(q);
- }
- private void dijkstra(final NavigableSet<Solmu> q) {
- Solmu u, v;
- while (!q.isEmpty()) {
- u = q.pollFirst();
- if (u.etaisyys == Integer.MAX_VALUE)
- break;
- for (Map.Entry<Solmu, Integer> a : u.naapurit.entrySet()) {
- v = a.getKey(); //the neighbour in this iteration
- final int alternateDist = u.etaisyys + a.getValue();
- if (alternateDist < v.etaisyys) {
- q.remove(v);
- v.etaisyys = alternateDist;
- v.edellinen = u;
- q.add(v);
- }
- }
- }
- }
- public int lyhyinPolku(String loppu) {
- if (!verkko.containsKey(loppu)) {
- return -1;
- }
- return verkko.get(loppu).etaisyys;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement