C10

package PAZ1b.cvicenie10;

import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import sk.upjs.paz.graph.*;

public class BellmanFord {

        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());
        }

        public Map<Vertex, Double> bellmanFord(Graph g, Vertex s) {
                Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);
                d.put(s, 0d);
                for (int i = 0; i < g.getVertices().size(); i++)
                        for (Edge e : g.getEdges())
                                relax(e, d);
                return d;
        }

        public List<Vertex> zrekonstruujCest(Vertex ciel, Map<Vertex, Double> mapaVzdialenosti, Graph g) {
                List<Vertex> cesta = new LinkedList<Vertex>();

                Vertex aktualny = ciel;
                cesta.add(aktualny);

                while (mapaVzdialenosti.get(aktualny) > 0) {
                        for (Vertex sused : aktualny.getOutNeighbours()) {
                                if (mapaVzdialenosti.get(aktualny) - g.getEdge(aktualny, sused).getWeight() == mapaVzdialenosti
                                                .get(sused)) {
                                        aktualny = sused;
                                        cesta.add(aktualny);
                                        break;
                                }
                        }
                }
                Collections.reverse(cesta);
                return cesta;
        }

        public static void vyhodVnutroCesty(Graph g, List<Vertex> cesta) {
                for (int i = 1; i < cesta.size() - 1; i++) {
                        g.removeVertex(cesta.get(i));
                }
        }

        public static void orezGraf(Graph g, double maximum) {
                // prejdem vsetky hrany
                Set<Edge> hrany = g.getEdges();
                Set<Edge> hranyDlhe = new HashSet<>();
                for (Edge hrana : hrany) {
                        // zistim ci je kratsia alebo dlhsia
                        if (hrana.getWeight() > maximum) {
                                // skusim ju odstranit ak je prilis dlha
                                hranyDlhe.add(hrana);
                        }
                }

                for (Edge dlhaHrana : hranyDlhe) {
                        g.removeEdge(dlhaHrana);
                }

        }

        public static void main(String[] args) {
                BellmanFord bf = new BellmanFord();
                Graph tatooine = Graph.createFromFile("graf.txt");
                System.out.println(tatooine);
                tatooine.setDirected(true);
                System.out.println(tatooine);

                orezGraf(tatooine, 23);
                System.out.println(tatooine);

                Map<Vertex, Double> mapaVzdialenosti = bf.bellmanFord(tatooine, tatooine.getVertex("C"));
                System.out.println(mapaVzdialenosti);

                List<Vertex> cesta = bf.zrekonstruujCest(tatooine.getVertex("A"), mapaVzdialenosti, tatooine);
                System.out.println(cesta);

                vyhodVnutroCesty(tatooine, cesta);
                System.out.println(tatooine);

                Map<Vertex, Double> mapaVzdialenosti2 = bf.bellmanFord(tatooine, tatooine.getVertex("C"));
                System.out.println(mapaVzdialenosti2);

                List<Vertex> cesta2 = bf.zrekonstruujCest(tatooine.getVertex("A"), mapaVzdialenosti2, tatooine);
                System.out.println(cesta2);
        }

}
 

A B: 2
A D: 5
B D: 1
B C: 7
D E: 2
C E: 3
A C: 20

 

package PAZ1b.cvicenie10;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import sk.upjs.paz.graph.*;

public class BellmanFordMatice {

        public void relax(int source, int target, Map<Integer, Double> d, int[][] g) {
                if (d.get(source) + g[source][target] < d.get(target))
                        d.put(target, d.get(source) + g[source][target]);
        }

        public Map<Integer, Double> bellmanFord(int[][] g, int s) {
                Map<Integer, Double> d = new HashMap<>();
                for (int i = 0; i < g.length; i++) {
                        d.put(i, Double.MAX_VALUE);
                }
                d.put(s, 0d);
                // idem tolko krat kolko mam vrcholov
                for (int i = 0; i < g.length; i++)
                        // nasledujuce cykly idu cez vsetky hrany
                        for (int j = 0; j < g.length; j++) {
                                for (int k = 0; k < g.length; k++) {
                                        if (g[j][k] != -1) {
                                                // relaxacia
                                                relax(j, k, d, g);
                                        }
                                }
                        }

                return d;
        }

//      public List<Vertex> zrekonstruujCest(Vertex ciel, Map<Vertex, Double> mapaVzdialenosti, Graph g) {
//              List<Vertex> cesta = new LinkedList<Vertex>();
//
//              Vertex aktualny = ciel;
//              cesta.add(aktualny);
//
//              while (mapaVzdialenosti.get(aktualny) > 0) {
//                      for (Vertex sused : aktualny.getOutNeighbours()) {
//                              if (mapaVzdialenosti.get(aktualny) - g.getEdge(aktualny, sused).getWeight() == mapaVzdialenosti
//                                              .get(sused)) {
//                                      aktualny = sused;
//                                      cesta.add(aktualny);
//                                      break;
//                              }
//                      }
//              }
//              Collections.reverse(cesta);
//              return cesta;
//      }

        public static void main(String[] args) {
//              BellmanFordMatice bf = new BellmanFordMatice();
//              Graph tatooine = Graph.createFromFile("graf.txt");
//              System.out.println(tatooine);
//              tatooine.setDirected(true);
//              System.out.println(tatooine);
//
//              Map<Vertex, Double> mapaVzdialenosti = bf.bellmanFord(tatooine, tatooine.getVertex("C"));
//              System.out.println(mapaVzdialenosti);

        }

}
 

package PAZ1b.cvicenie10;

import sk.upjs.jpaz2.*;

public class Launcher {

        public static void main(String[] args) {
                int cislo = Integer.MAX_VALUE;
                System.out.println(cislo);
                System.out.println(cislo+1);
                System.out.println(Integer.MIN_VALUE);
                System.out.println(Double.POSITIVE_INFINITY);
                System.out.println(Double.POSITIVE_INFINITY+1);

        }
}