Zdrojový kód k prednáške o najkratších cestách

import java.util.*;
import sk.upjs.paz.graph.*;

public class NajCesty {

        /**
         * Graf skumany grafovymi algoritmami.
         */
        private Graph g;

        /**
         * Konstruktor triedy implementujucej algoritmy hladania najkratsich ciest.
         */
        public NajCesty(Graph g) {
                this.g = g;
                if (!g.isDirected())
                        throw new RuntimeException("Akceptovane su len orientovane grafy.");
        }

        /**
         * Zrelaxuje orientovanu hranu e s vyuzitim odhadov v mape d.
         *
         * @param e
         *            relaxovana orientovana hrana
         * @param d
         *            mapa s hornymi odhadmi vzdialenosti
         */
        public void relax(Edge e, Map<Vertex, Double> d) {
                Vertex u = e.getSource();
                Vertex v = e.getTarget();
                if (d.get(u) + e.getWeight() < d.get(v))
                        d.put(v, d.get(u) + e.getWeight());
        }

        /**
         * Vytvori map-u najkratsich ciest zo startovacieho vrcholu s do vsetkych
         * vrcholov grafu aplikovanim Bellman-Fordovho algoritmu (pre grafy
         * neobsahujuce zaporny cyklus)
         *
         * @param s
         *            startovaci vrchol
         */
        public Map<Vertex, Double> bellmanFord(Vertex s) {
                // Vytvorime map, v ktorom budeme pre kazdy vrchol udrziavat aktualny
                // horny odhad dlzky najkratsej cesty z s do tohto vrcholu
                Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);

                // Pre startovaci vrchol nastavime odhad na 0
                d.put(s, 0d);

                // n-krat opakujeme relaxaciu vsetkych hran
                for (int i = 0; i < g.getVertices().size(); i++)
                        for (Edge e : g.getEdges())
                                relax(e, d);

                return d;
        }

        /**
         * Vytvori map-u najkratsich ciest zo startovacieho vrcholu s do vsetkych
         * vrcholov grafu aplikovanim Dijkstrovho algoritmu (pre grafy s nezapornymi
         * cenami hran)
         *
         * @param s
         *            startovaci vrchol
         */
        public Map<Vertex, Double> dijkstra(Vertex s) {
                // Vytvorime map, v ktorom budeme pre kazdy vrchol udrziavat aktualny
                // horny odhad dlzky najkratsej cesty z s do tohto vrcholu
                Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);
                // Pre startovaci vrchol nastavime odhad na 0
                d.put(s, 0d);

                Set<Vertex> nevybavene = new HashSet<Vertex>(g.getVertices());
                while (!nevybavene.isEmpty()) {
                        // Vyberieme vrchol, ktory spomedzi nevybavenych ma najmensi
                        // medzivysledok d
                        Vertex vybrany = nevybavene.iterator().next();
                        for (Vertex v : nevybavene)
                                if (d.get(v) < d.get(vybrany))
                                        vybrany = v;

                        // Nechame zrelaxovat vsetky z neho vychadzajuce hrany
                        for (Edge e : vybrany.getOutEdges())
                                relax(e, d);

                        // Vybrany vrchol vyberieme z mnoziny nevybavenych
                        nevybavene.remove(vybrany);
                }

                return d;
        }

        /**
         * Len nacrt kodu Floyd-Warshallowho algoritmu.
         */
        public void fw() {
                // Vyrobime ohodnotenu maticu susednosti
                Vertex[] vrcholyVPoli = g.createVertexArray();
                double[][] d = g.createWeightedAdjacencyMatrix(vrcholyVPoli,
                                Double.POSITIVE_INFINITY);

                // Do n si ulozime pocet vrcholov grafu
                int n = vrcholyVPoli.length;

                // Aplikujeme algoritmus dynamickeho programovania
                for (int k = 0; k < n; k++)
                        for (int i = 0; i < n; i++)
                                for (int j = 0; j < n; j++)
                                        if (d[i][k] + d[k][j] < d[i][j])
                                                d[i][j] = d[i][k] + d[k][j];

                // Tu mozeme "vypisat" najkratsie vzajomne vzdialenosti medzi vrcholmi
                // alebo spravit inu akciu s vypocitanym polom d
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Nacitame neorientovany graf
                Graph mapa = Graph.createFromFile("graf.txt");
                // Transformujeme vsetky hrany grafu na orientovane
                mapa.setDirected(true);

                NajCesty nc = new NajCesty(mapa);
                System.out.println(nc.dijkstra(mapa.getVertex("A")));
        }

}

import java.awt.Color;
import java.util.*;
import sk.upjs.paz.graph.*;
import sk.upjs.paz.graphvisualizer.GraphVisualizer;

public class NajCestyViz {

        /**
         * Graf skumany grafovymi algoritmami.
         */
        private Graph g;

        private GraphVisualizer gv;

        /**
         * Konstruktor triedy implementujucej algoritmy hladania najkratsich ciest.
         */
        public NajCestyViz(Graph g) {
                this.g = g;
                gv = new GraphVisualizer(g);
                if (!g.isDirected())
                        throw new RuntimeException("Akceptovane su len orientovane grafy.");
        }

        /**
         * Zrelaxuje orientovanu hranu e s vyuzitim odhadov v mape d.
         *
         * @param e
         *            relaxovana orientovana hrana
         * @param d
         *            mapa s hornymi odhadmi vzdialenosti
         */
        public void relax(Edge e, Map<Vertex, Double> d) {
                Vertex u = e.getSource();
                Vertex v = e.getTarget();
                if (d.get(u) + e.getWeight() < d.get(v))
                        d.put(v, d.get(u) + e.getWeight());
        }

        /**
         * Vytvori map-u najkratsich ciest zo startovacieho vrcholu s do vsetkych
         * vrcholov grafu aplikovanim Bellman-Fordovho algoritmu (pre grafy
         * neobsahujuce zaporny cyklus)
         *
         * @param s
         *            startovaci vrchol
         */
        public Map<Vertex, Double> bellmanFord(Vertex s) {
                // Vytvorime map, v ktorom budeme pre kazdy vrchol udrziavat aktualny
                // horny odhad dlzky najkratsej cesty z s do tohto vrcholu
                Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);

                // Pre startovaci vrchol nastavime odhad na 0
                d.put(s, 0d);

                gv.addToMonitor("d", d);
                gv.pause("Inicializacia");

                // n-krat opakujeme relaxaciu vsetkych hran
                for (int i = 0; i < g.getVertices().size(); i++) {
                        for (Edge e : g.getEdges())
                                relax(e, d);

                        gv.pause("Po " + (i + 1) + "-tej relaxacii vsetkych hran.");
                }

                gv.removeFromMonitor(d);
                return d;
        }

        /**
         * Vytvori map-u najkratsich ciest zo startovacieho vrcholu s do vsetkych
         * vrcholov grafu aplikovanim Dijkstrovho algoritmu (pre grafy s nezapornymi
         * cenami hran)
         *
         * @param s
         *            startovaci vrchol
         */
        public Map<Vertex, Double> dijkstra(Vertex s) {
                // Vytvorime map, v ktorom budeme pre kazdy vrchol udrziavat aktualny
                // horny odhad dlzky najkratsej cesty z s do tohto vrcholu
                Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);
                // Pre startovaci vrchol nastavime odhad na 0
                d.put(s, 0d);

                Set<Vertex> nevybavene = new HashSet<Vertex>(g.getVertices());
                gv.addToMonitor("d", d);
                gv.addToMonitor("nevybavene", nevybavene);
                gv.pause("Po inicializacii.");

                while (!nevybavene.isEmpty()) {
                        // Vyberieme vrchol, ktory spomedzi nevybavenych ma najmensi
                        // medzivysledok d
                        Vertex vybrany = nevybavene.iterator().next();
                        for (Vertex v : nevybavene)
                                if (d.get(v) < d.get(vybrany))
                                        vybrany = v;

                        gv.setColor(vybrany, Color.red);
                        gv.pause("Vybrany vrchol " + vybrany);

                        // Nechame zrelaxovat vsetky z neho vychadzajuce hrany
                        for (Edge e : vybrany.getOutEdges()) {
                                gv.setColor(e, Color.green);
                                gv.pause("Pred relaxaciou " + e);
                                relax(e, d);
                                gv.pause("Po relaxacii " + e);
                                gv.resetColor(e);
                        }

                        // Vybrany vrchol vyberieme z mnoziny nevybavenych
                        nevybavene.remove(vybrany);

                        gv.pause("Po relaxacii hran iducich z " + vybrany);
                        gv.resetColor(vybrany);
                }

                gv.pause("Po skonceni Dijkstrovho algoritmu.");
                return d;
        }

        /**
         * Len nacrt kodu Floyd-Warshallowho algoritmu.
         */
        public void fw() {
                // Vyrobime ohodnotenu maticu susednosti
                Vertex[] vrcholyVPoli = g.createVertexArray();
                double[][] d = g.createWeightedAdjacencyMatrix(vrcholyVPoli,
                                Double.POSITIVE_INFINITY);

                // Do n si ulozime pocet vrcholov grafu
                int n = vrcholyVPoli.length;

                // Aplikujeme algoritmus dynamickeho programovania
                for (int k = 0; k < n; k++)
                        for (int i = 0; i < n; i++)
                                for (int j = 0; j < n; j++)
                                        if (d[i][k] + d[k][j] < d[i][j])
                                                d[i][j] = d[i][k] + d[k][j];

                // Tu mozeme "vypisat" najkratsie vzajomne vzdialenosti medzi vrcholmi
                // alebo spravit inu akciu s vypocitanym polom d
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Nacitame neorientovany graf
                Graph mapa = Graph.createFromFile("graf.txt");
                // Transformujeme vsetky hrany grafu na orientovane
                mapa.setDirected(true);

                NajCestyViz nc = new NajCestyViz(mapa);
                System.out.println(nc.dijkstra(mapa.getVertex("A")));
        }
}