Zdrojový kód z prednášky 24.4.2012

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

public class Grafy {

        // Relaxacia orientovanej hrany
        public static 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());
        }

        // Bellman-Fordov algoritmus
        public static Map<Vertex, Double> bellmanFord(Graph g, Vertex s) {
                // Iba orientovane grafy su akceptovane ako vstup
                if (!g.isDirected())
                        throw new RuntimeException(
                                        "Len orientovane grafy su akceptovane pre Bellman-Fordov algoritmus");

                // Vytvorime map, v ktorom budeme pre kazdy vrchol udrziavat aktualny
                // horny odhad dlzky najkratsej cesty z s do tohto vrcholu
                Map<Vertex, Double> d = new HashMap<Vertex, Double>();

                // Inicializacia predbeznych najkratsich vzdialenosti
                for (Vertex v : g.getVertices())
                        d.put(v, Double.POSITIVE_INFINITY);
                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;
        }

        public static void main(String[] args) {
                Graph mapa = new Graph();
                mapa.loadFromFile("graf.txt");
                mapa.setDirected(true);
                System.out.println(bellmanFord(mapa, mapa.getVertex("A")));
        }
}

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

public class Grafy {

        // Relaxacia orientovanej hrany
        public static 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());
        }

        // Dijkstrov algoritmus
        public static Map<Vertex, Double> dijkstra(Graph g, Vertex s) {
                // Iba orientovane grafy su akceptovane ako vstup
                if (!g.isDirected())
                        throw new RuntimeException(
                                        "Len orientovane grafy su akceptovane pre Dijkstrov algoritmus");

                // Vytvorime map, v ktorom budeme pre kazdy vrchol udrziavat aktualny
                // horny odhad dlzky najkratsej cesty z s do tohto vrcholu
                Map<Vertex, Double> d = new HashMap<Vertex, Double>();

                // Inicializacia predbeznych najkratsich vzdialenosti
                for (Vertex v : g.getVertices())
                        d.put(v, Double.POSITIVE_INFINITY);
                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;
        }

        public static void main(String[] args) {
                Graph mapa = new Graph();
                mapa.loadFromFile("graf.txt");
                mapa.setDirected(true);
                System.out.println(mapa);
                System.out.println(dijkstra(mapa, mapa.getVertex("A")));
        }
}

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

public class Grafy {

        // Floyd-Warshallov algoritmus
        public static void fw(Graph g) {
                // Vyrobime pole vrcholov
                Vertex[] vrcholy = new Vertex[g.getVertices().size()];
                int idx = 0;
                for (Vertex v : g.getVertices()) {
                        vrcholy[idx] = v;
                        idx++;
                }

                // Vyrobime pole, do ktoreho budeme davat vzajomne vzdialenosti
                double[][] d = new double[vrcholy.length][vrcholy.length];
                for (int i = 0; i < vrcholy.length; i++)
                        for (int j = 0; j < vrcholy.length; j++)
                                if (g.hasEdge(vrcholy[i], vrcholy[j]))
                                        d[i][j] = g.getEdge(vrcholy[i], vrcholy[j]).getWeight();
                                else
                                        d[i][j] = Double.POSITIVE_INFINITY;

                // Aplikujeme algoritmus dynamickeho programovania
                for (int k = 0; k < vrcholy.length; k++)
                        for (int i = 0; i < vrcholy.length; i++)
                                for (int j = 0; j < vrcholy.length; 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
        }

        public static void main(String[] args) {
                Graph mapa = new Graph();
                mapa.loadFromFile("graf.txt");
                mapa.setDirected(true);
                fw(mapa);
        }
}