/ Published in: Java
Program izraÄunava najkraći put u zadanom grafu.
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
package org.foi.dstg.tikomlino; import java.util.Iterator; import java.util.Map; /** * * @author tinkomlinovic */ public class Dijkstra { try { boolean ponovi = true; while (ponovi) { boolean sviSuZavrsili = true; while (i.hasNext()) { Vrh v = (Vrh) trenutniVrhEntry.getValue(); if (!v.isZavrsio()) { sviSuZavrsili = false; } } if (sviSuZavrsili) { ponovi = false; } vrhovi = korak(vrhovi); } while (it.hasNext()) { Vrh vrh = (Vrh) vrhoviEntry.getValue(); System.out.println("Vrh: " + vrh.getNaziv() + ", Udaljenost: " + vrh.getNajkraciPut() + ", Vrh preko kojeg je dobio oznaku: " + vrh.getVrhPrekoKojegJeDobioOznaku()); } } } } while (iterator.hasNext()) { Vrh vrh = (Vrh) vrhEntry.getValue(); if (!vrh.isZavrsio()) { while (i.hasNext()) { Vrh susjedniVrh = vrhovi.get(nazivSusjednogVrha); if (susjedniVrh.isZavrsio()) { int udaljenostSusjednogVrhaOdPocetnogVrha = susjedniVrh.getNajkraciPut(); if (vrh.getNajkraciPut() > udaljenostOdSusjednogVrha + udaljenostSusjednogVrhaOdPocetnogVrha) { vrh.setNajkraciPut(udaljenostOdSusjednogVrha + udaljenostSusjednogVrhaOdPocetnogVrha); vrh.setVrhPrekoKojegJeDobioOznaku(nazivSusjednogVrha); } } } vrhovi.put(nazivVrha, vrh); } } Vrh vrhKojiZavrsava = null; while (i.hasNext()) { Vrh vrh = (Vrh) vrhEntry.getValue(); if (vrh.getNajkraciPut() < najmanjaUdaljenost && !vrh.isZavrsio()) { najmanjaUdaljenost = vrh.getNajkraciPut(); vrhKojiZavrsava = vrh; } } if (vrhKojiZavrsava != null) { vrhKojiZavrsava.setZavrsio(true); vrhovi.put(vrhKojiZavrsava.getNaziv(), vrhKojiZavrsava); } return vrhovi; } } package org.foi.dstg.tikomlino.files; import java.io.BufferedInputStream; import java.io.DataInputStream; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.util.ArrayList; import java.util.List; /** * * @author tinkomlinovic */ //Todo promijniti hardkodiranu adresu u path List<String> redovi = new ArrayList<String>(); try { // Here BufferedInputStream is added for fast reading. // dis.available() returns 0 if the file does not have more lines. while (dis.available() != 0) { // this statement reads the line from the file and print it to // the console. redovi.add(dis.readLine()); } // dispose all the resources after using them. fis.close(); bis.close(); dis.close(); } return redovi; } } package org.foi.dstg.tikomlino.files; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.regex.Matcher; import java.util.regex.Pattern; import org.foi.dstg.tikomlino.Vrh; /** * * @author tinkomlinovic */ int i = 0; if (i == 0) { Pattern p = Pattern.compile("[a-z,0-9,A-Z]*"); Matcher m = p.matcher(red); if (m.find()) { prviVrh = red; i++; } else { } } else { Pattern p = Pattern.compile("[a-z,0-9,A-Z]*,[a-z,0-9,A-Z]*,[0-9]*"); Matcher m = p.matcher(red); //Regex je u redu if (m.find()) { //Prvi vrh if (vrhovi.containsKey(naziv1)) { Vrh vrh = vrhovi.get(naziv1); vrhovi.remove(naziv1); vrh.dodajSusjedniVrh(naziv2, udaljenost); vrhovi.put(naziv1, vrh); } else { Vrh vrh = new Vrh(); vrh.setNaziv(naziv1); vrh.dodajSusjedniVrh(naziv2, udaljenost); if (naziv1.equals(prviVrh)){ vrh.setZavrsio(true); vrh.setNajkraciPut(0); vrh.setZadnji(false); } else{ vrh.setZavrsio(false); } vrhovi.put(naziv1, vrh); } } else { } } } return vrhovi; } } package org.foi.dstg.tikomlino; import java.util.HashMap; import java.util.Map; import org.foi.dstg.tikomlino.files.FileReader; import org.foi.dstg.tikomlino.files.Parser; /** * * @author tinkomlinovic */ public class Main { /** * @param args the command line arguments */ if (args.length == 1){ vrhovi = parser.parseRows(fileReader.readFile(args[0])); Dijkstra dijkstra = new Dijkstra(); dijkstra.izvrsiAlgoritam(vrhovi); } else { } } } package org.foi.dstg.tikomlino; import java.util.HashMap; import java.util.Map; /** * * @author tinkomlinovic */ public class Vrh { private int najkraciPut; private boolean zavrsio; //false - zavrsio private boolean zadnji; // true - zadnji vrh koji je dobio oznaku return naziv; } this.naziv = naziv; } return udaljenostSusjednogVrha; } udaljenostSusjednogVrha.put(naziv, udaljenost); } public int getNajkraciPut() { return najkraciPut; } public void setNajkraciPut(int najkraciPut) { this.najkraciPut = najkraciPut; } public boolean isZavrsio() { return zavrsio; } public void setZavrsio(boolean konacnaOznaka) { this.zavrsio = konacnaOznaka; } return vrhPrekoKojegJeDobioOznaku; } this.vrhPrekoKojegJeDobioOznaku = vrhPrekoKojegJeDobioOznaku; } public boolean isZadnji() { return zadnji; } public void setZadnji(boolean zadnji) { this.zadnji = zadnji; } }