граф / DirectedGraph

import java.util.*;

/**
*
* @param <T> type of vertex
*/

public class DirectedGraph<T> {

private static final Integer MAX_VALUE = 1000;

public class Edge{

private final T vertexDestination;
private final int distance;

public Edge(T destination, int distance){
vertexDestination = destination;
this.distance = distance;
}

@Override
public String toString() {
return "Edge [vertex=" + vertexDestination + ", cost=" + distance + "]";
}

}

private final Map<T, List<Edge>> vertexes = new HashMap<>();

/**
*
* @return vertexes map
*/

public Map<T, List<Edge>> getVertexes() {
return vertexes;
}

/**
* adds vertex
* @param vertex vertex to be added
*/
public void addVertex(T vertex) {
if (vertexes.containsKey(vertex))
return;
vertexes.put(vertex, new ArrayList<>());
}

/**
* adds edge
* @param from starting point of edge
* @param to ending point of edge
* @param distance distance between vertexes
*/

public void addEdge(T from, T to, int distance) {
this.addVertex(from);
this.addVertex(to);
vertexes.get(from).add(new Edge(to, distance));
}

/**
*
* @param from starting point of edge
* @param to ending point of edge
* @return true if there is edge from 'from' vertexes to 'to' vertex, false otherwise
*/

public boolean isEdge(T from, T to) {
for(Edge edge : vertexes.get(from)){
if(edge.vertexDestination.equals(to)) {
return true;
}
}
return false;
}

/**
*
* @param from starting point of edge
* @param to ending point of edge
* @return distance between edges
*/

public int getDistance(T from, T to) {
for(Edge edge : vertexes.get(from)){
if(edge.vertexDestination.equals(to))
return edge.distance;
}
return -1;
}

/**
*
* @return matrix if distances
*/

public List<List<Integer>> createMatrix(){
List<List<Integer>> result = new ArrayList<>();
vertexes.forEach((key, value) -> {
List<Integer> innerResult = new ArrayList<>();
vertexes.forEach((innerKey, innerValue) -> {
int distance = getDistance(innerKey, key);
innerResult.add(distance != -1
? distance
: 0);
});
result.add(innerResult);
});
return result;
}

/**
*
* @param pathArray shortest distances from key to pathArray.get(i)
* @param shortestPathSet is shortest path already found for shortestPathSet.get(i)
* @return minimal distance
*/

private int minDistance(List<Integer> pathArray, List<Boolean> shortestPathSet) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
for (int i = 0; i < vertexes.size(); i++)
if (!shortestPathSet.get(i) && pathArray.get(i) <= min) {
min = pathArray.get(i);
minIndex = i;
}

return minIndex;
}

/**
*
* @param matrix matrix with distances between edges
* @param key vertex distances will be calculated for
* @return list of distances between key vertex and result.get(i)
*/

public List<Integer> minDistancesDijkstra(List<List<Integer>> matrix, Integer key) {
List<Integer> pathArray = new ArrayList<>();

List<Boolean> shortestPathSet = new ArrayList<>();

for (int i = 0; i < vertexes.size(); i++) {
pathArray.add(i, Integer.MAX_VALUE);
shortestPathSet.add(i, false);
}

pathArray.set(key, 0);

for (int count = 0; count < vertexes.size() - 1; count++) {
int u = minDistance(pathArray, shortestPathSet);
shortestPathSet.set(u, true);
for (int i = 0; i < vertexes.size(); i++)
if (!shortestPathSet.get(i)
&& matrix.get(u).get(i)
!= 0 && pathArray.get(u) !=
Integer.MAX_VALUE && pathArray.get(u)
+ matrix.get(u).get(i) < pathArray.get(i)){
pathArray.set(i, pathArray.get(u)
+ matrix.get(u).get(i));
}
}

return pathArray;
}

/**
*
* @param graph matrix with distances between vertexes, 0 means infinite (vertex cannot be reached)
* @throws NullPointerException if graph is null
*/

public List<List<Integer>> floydWarshall(List<List<Integer>> graph) {
List<List<Integer>> result = new ArrayList<>();

for (int i = 0; i < graph.size(); i++) {
result.add(new ArrayList<>());
for (int j = 0; j < graph.size(); j++) {
result.get(i).add(j, graph.get(i).get(j));
}
}

for (int i = 0; i < graph.size(); i++) {
for (int j = 0; j < graph.size(); j++) {
if (result.get(i).get(j) == 0) {
result.get(i).set(j, MAX_VALUE);
}
}
}

for (int k = 0; k < graph.size(); k++) {
for (int i = 0; i < graph.size(); i++) {
for (int j = 0; j < graph.size(); j++) {
if (result.get(i).get(k) + result.get(k).get(j) < result.get(i).get(j))
result.get(i).set(j, result.get(i).get(k) + result.get(k).get(j));
}
}
}

for (int i = 0; i < graph.size(); i++) {
for (int j = 0; j < graph.size(); j++) {
if (i == j) {
result.get(i).set(j, 0);
}
}
}

return result;
}
}