D9

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import sk.upjs.paz.Edge;
import sk.upjs.paz.Graph;
import sk.upjs.paz.Vertex;

public class NajkratsieCesty {

        Map<Vertex, Vertex> predchodcovia = new HashMap<Vertex, Vertex>();

        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());
                        predchodcovia.put(v, u);
                }
        }

        public Map<Vertex, Double> dijkstra(Graph g, Vertex s) {
                Map<Vertex, Double> d = new HashMap<Vertex, Double>();

                for (Vertex v : g.getVertices())
                        d.put(v, Double.POSITIVE_INFINITY);
                d.put(s, 0d);

                Set<Vertex> q = new HashSet<Vertex>();
                q.addAll(g.getVertices());

                while (!q.isEmpty()) {
                        double min = Double.POSITIVE_INFINITY;
                        Vertex minVertex = null;

                        for (Vertex v : q) {
                                if (d.get(v) <= min) {
                                        min = d.get(v);
                                        minVertex = v;
                                }
                        }

                        //System.out.println(minVertex.getLabel());

                        for (Edge e : minVertex.getOutEdges())
                                this.relax(e, d);

                        q.remove(minVertex);
                }

                return d;

        }


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

                NajkratsieCesty nc = new NajkratsieCesty();

                System.out.println(nc.dijkstra(g, g.getVertex("1")));
        }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import sk.upjs.paz.graph.Edge;
import sk.upjs.paz.graph.Graph;
import sk.upjs.paz.graph.Vertex;

public class NajkratsieCesty {

        Map<Vertex, Vertex> predchodcovia = new HashMap<Vertex, Vertex>();

        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());
                        predchodcovia.put(v, u);
                }
        }

        public Map<Vertex, Double> dijkstra(Graph g, Vertex s) {
                Map<Vertex, Double> d = new HashMap<Vertex, Double>();

                for (Vertex v : g.getVertices())
                        d.put(v, Double.POSITIVE_INFINITY);
                d.put(s, 0d);

                Set<Vertex> q = new HashSet<Vertex>();
                q.addAll(g.getVertices());

                while (!q.isEmpty()) {
                        double min = Double.POSITIVE_INFINITY;
                        Vertex minVertex = null;

                        for (Vertex v : q) {
                                if (d.get(v) <= min) {
                                        min = d.get(v);
                                        minVertex = v;
                                }
                        }

                        // System.out.println(minVertex.getLabel());

                        for (Edge e : minVertex.getOutEdges())
                                this.relax(e, d);

                        q.remove(minVertex);
                }

                return d;

        }

        public ArrayList<Integer> najkratsiaCesta(Vertex start, Vertex ciel) {

                ArrayList<Integer> cesta = new ArrayList<Integer>();
                while (ciel != start) {
                        cesta.add(Integer.parseInt(ciel.getLabel()));
                        ciel = predchodcovia.get(ciel);
                }
                cesta.add(Integer.parseInt(start.getLabel()));
                return cesta;
        }

        public ArrayList<Integer> najkratsiaCesta2(Vertex start, Vertex ciel,
                        Map<Vertex, Double> vzdialenosti) {
                ArrayList<Integer> cesta = new ArrayList<Integer>();

                while (ciel != start) {
                        cesta.add(Integer.parseInt(ciel.getLabel()));
                        for (Edge hrana : ciel.getInEdges()) {
                                double vzdialenost = vzdialenosti.get(ciel);
                                if ((vzdialenost - hrana.getWeight()) == vzdialenosti.get(hrana
                                                .getSource())) {
                                        ciel = hrana.getSource();
                                        break;
                                }
                        }
                }
                cesta.add(Integer.parseInt(start.getLabel()));
                return cesta;
        }

        public void floydWarshal(int[][] matica) {
                double[][] odhady = new double[matica.length][matica.length];

                for (int j = 0; j < odhady.length; j++) {
                        for (int i = 0; i < odhady.length; i++) {
                                if (i != j)
                                        odhady[i][j]= Double.POSITIVE_INFINITY;
                                else
                                        odhady[i][i] = 0;
                        }
                }
                for (int k=0; k<odhady.length; k++)
                        for (int i=0; i<odhady.length; i++)
                        for (int j=0; j<odhady.length; j++)
                        if (matica[i][k] + matica[k][j] < odhady[i][j])
                        odhady[i][j] = matica[i][k] + matica[k][j];
        }

        public static void main(String[] args) {
                Graph g = new Graph();
                g.loadFromFile("graf.txt");
                g.setDirected(false);

                for (Edge hrana : g.getEdges()) {
                        System.out.println(hrana.getSource() + " " + hrana.getTarget());
                }

                NajkratsieCesty nc = new NajkratsieCesty();
                System.out.println(nc.dijkstra(g, g.getVertex("1")));
                System.out.println(nc.najkratsiaCesta(g.getVertex("1"),
                                g.getVertex("3")));
                System.out.println(nc.najkratsiaCesta2(g.getVertex("1"),
                                g.getVertex("3"), nc.dijkstra(g, g.getVertex("1"))));
        }
}