versione1 es4

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

class GraphNode {
    public int id;
    public Map<Integer, Integer> neighbors;

    public GraphNode(int id) {
        this.id = id;
        this.neighbors = new HashMap<>();
    }

    public int getId() {
        return id;
    }

    public Map<Integer, Integer> getNeighbors() {
        return neighbors;
    }

    public void addNeighbor(GraphNode neighbor, int weight) {
        neighbors.put(neighbor.getId(), weight);
        neighbor.neighbors.put(this.id, weight); // Bidirectional edge
    }

    public void removeNeighbor(GraphNode neighbor) {
        neighbors.remove(neighbor.getId());
        neighbor.neighbors.remove(this.id);
    }

    public boolean hasNeighbor(GraphNode neighbor) {
        return neighbors.containsKey(neighbor.getId());
    }

    public Integer getWeightToNeighbor(GraphNode neighbor) {
        return neighbors.get(neighbor.getId());
    }


    public Map<GraphNode, Integer> bellmanFordShortestPaths(GraphNode source) {
        Map<GraphNode, Integer> distanceMap = new HashMap<>();
        Map<GraphNode, List<GraphNode>> shortestPaths = new HashMap<>();

        for (GraphNode node : getNeighbors().keySet()) {
            distanceMap.put(node, Integer.MAX_VALUE);
            shortestPaths.put(node, new ArrayList<>());
        }

        distanceMap.put(source, 0);
        shortestPaths.get(source).add(source);

        for (int i = 0; i < getNeighbors().size() - 1; i++) {
            for (GraphNode node : getNeighbors().keySet()) {
                for (Map.Entry<GraphNode, Integer> neighborEntry : node.getNeighbors().entrySet()) {
                    int newDistance = distanceMap.get(node) + neighborEntry.getValue();
                    if (newDistance < distanceMap.get(neighborEntry.getKey())) {
                        distanceMap.put(neighborEntry.getKey(), newDistance);
                        shortestPaths.get(neighborEntry.getKey()).clear();
                        shortestPaths.get(neighborEntry.getKey()).addAll(shortestPaths.get(node));
                        shortestPaths.get(neighborEntry.getKey()).add(neighborEntry.getKey());
                    }
                }
            }
        }

        printShortestPaths(source, distanceMap, shortestPaths);

        return distanceMap;
    }

    // Print shortest paths
    private void printShortestPaths(GraphNode source, Map<GraphNode, Integer> distanceMap, Map<GraphNode, List<GraphNode>> shortestPaths) {
        System.out.println("s d dist path");
        System.out.println("---- ---- ------------ -------------------");

        for (GraphNode node : getNeighbors().keySet()) {
            System.out.printf("%d %d %.4f %s%n", source.getId(), node.getId(), distanceMap.get(node) / 1.0,
                    buildPathString(shortestPaths.get(node)));
        }
    }

    private String buildPathString(List<GraphNode> path) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            sb.append(path.get(i).getId());
            if (i < path.size() - 1) {
                sb.append("->");
            }
        }
        return sb.toString();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("ID: ").append(id).append(", Neighbors: [");
        for (int neighborId : neighbors.keySet()) {
            int weight = neighbors.get(neighborId);
            sb.append(neighborId).append(" (Weight: ").append(weight).append("), ");
        }
        sb.append("]");
        return sb.toString();
    }

}



public class Esercizio4 {

    public static void main(String[] args) {

        GraphNode node0 = new GraphNode(0);
        GraphNode node1 = new GraphNode(1);
        GraphNode node2 = new GraphNode(2);
        GraphNode node3 = new GraphNode(3);
        GraphNode node4 = new GraphNode(4);
        GraphNode node5 = new GraphNode(5);
        GraphNode node6 = new GraphNode(6);
        GraphNode node7 = new GraphNode(7);
        GraphNode node8 = new GraphNode(8);
        GraphNode node9 = new GraphNode(9);
        GraphNode node10 = new GraphNode(10);
        GraphNode node11 = new GraphNode(11);

        node0.addNeighbor(node1, 1);

        node1.addNeighbor(node11, 1);
        node1.addNeighbor(node5, 4);
        node1.addNeighbor(node4, 1);

        node2.addNeighbor(node8, 1);
        node2.addNeighbor(node5, 1);

        node5.addNeighbor(node6, 1);

        node11.addNeighbor(node8, 1);

        node6.addNeighbor(node3, 1);
        node6.addNeighbor(node4, 1);

        node4.addNeighbor(node7, 1);

        node7.addNeighbor(node9, 1);

        node9.addNeighbor(node10, 1);
        node9.addNeighbor(node3, 1);

        node10.addNeighbor(node3, 1);



        //int weightFromNode1ToNode2 = node1.getWeightToNeighbor(node2);
        //System.out.println("Weight from Node 1 to Node 2: " + weightFromNode1ToNode2);

        Map<GraphNode, Integer> distanceMap = node0.bellmanFordShortestPaths(node0);

        for (Map.Entry<GraphNode, Integer> entry : distanceMap.entrySet()) {
            System.out.println("Shortest distance from Node 0 to Node " + entry.getKey().getId() + ": " + entry.getValue());
        }
    }
}