package algorithms.graph;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

import datastructures.graph.AbstractGraph;
import datastructures.graph.DirectedGraph;
import datastructures.graph.Edge;
import datastructures.graph.Vertex;
import datastructures.util.GraphUtil;

public class FloydWarshallShortestPath {
  private AbstractGraph<String> graph = null;
  private Integer[][] distancesMatrix = null;
  private Vertex<String>[][] pathMatrix = null;
  private Map<Vertex<String>, Integer> indexesMap = null;
  private int numVertices = 0;

  public FloydWarshallShortestPath() {
    graph = new DirectedGraph<String>();
    indexesMap = new HashMap<Vertex<String>, Integer>();
  }

  @SuppressWarnings("unchecked")
  public void constructGraph(String[] input) {
    GraphUtil.constructGraph(graph, input);

    numVertices = graph.numVertices();
    Set<Vertex<String>> vertices = graph.verticesSet();
    Set<Edge<String>> edges = graph.edgesSet();
    distancesMatrix = new Integer[numVertices][numVertices];
    pathMatrix = new Vertex[numVertices][numVertices];
    int index = 0;

    for (Vertex<String> vertex : vertices) {
      indexesMap.put(vertex, index++);
    }

    for (int i = 0; i < numVertices; i++) {
      for (int j = 0; j < numVertices; j++) {
        if (i == j) {
          distancesMatrix[i][j] = 0;
        } else {
          distancesMatrix[i][j] = Integer.MAX_VALUE;
        }
        pathMatrix[i][j] = null;
      }
    }

    for (Edge<String> edge : edges) {
      int i = indexesMap.get(edge.sourceVertex);
      int j = indexesMap.get(edge.destVertex);

      distancesMatrix[i][j] = edge.weight;
      pathMatrix[i][j] = edge.sourceVertex;
    }
  }

  public void computeShortestPath() {
    for (int k = 0; k < numVertices; k++) {
      for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
          int distanceIJ = distancesMatrix[i][j];
          int distanceIK = distancesMatrix[i][k];
          int distanceKJ = distancesMatrix[k][j];

          int distancesSum = (distanceIK == Integer.MAX_VALUE || distanceKJ == Integer.MAX_VALUE) ? Integer.MAX_VALUE
              : (distanceIK + distanceKJ);

          if (distanceIJ > distancesSum) {
            distancesMatrix[i][j] = distancesSum;
            pathMatrix[i][j] = pathMatrix[k][j];
          }
        }
      }
    }
  }

  public Integer getShortestDistanceTo(String vertex1Label, String vertex2Label) {
    Vertex<String> vertex1 = graph.getVertex(vertex1Label);
    Vertex<String> vertex2 = graph.getVertex(vertex2Label);

    if (vertex1 == null || vertex2 == null) {
      return Integer.MAX_VALUE;
    }

    int i = indexesMap.get(vertex1);
    int j = indexesMap.get(vertex2);

    return distancesMatrix[i][j];
  }
}
@@ -37,23 +37,74 @@
 va.util.
-HashMap
+ArrayList;%0Aimport java.util.HashMap;%0Aimport java.util.List
 ;%0Aimport
@@ -2473,23 +2473,22 @@
 (String 
-vertex1
+source
 Label, S
@@ -2493,23 +2493,20 @@
  String 
-vertex2
+dest
 Label) %7B
@@ -2525,23 +2525,28 @@
 String%3E 
-v
+sourceV
 ertex
-1
  = graph
@@ -2556,23 +2556,22 @@
 tVertex(
-vertex1
+source
 Label);%0A
@@ -2589,23 +2589,26 @@
 String%3E 
-v
+destV
 ertex
-2
  = graph
@@ -2618,23 +2618,20 @@
 tVertex(
-vertex2
+dest
 Label);%0A
@@ -2639,23 +2639,28 @@
     if (
-v
+sourceV
 ertex
-1
  == null
@@ -2663,23 +2663,26 @@
 null %7C%7C 
-v
+destV
 ertex
-2
  == null
@@ -2755,15 +2755,20 @@
 get(
-v
+sourceV
 ertex
-1
 );%0A 
@@ -2797,15 +2797,18 @@
 get(
-v
+destV
 ertex
-2
 );%0A%0A
@@ -2844,10 +2844,920 @@
 %5Bj%5D;%0A  %7D
+%0A%0A  public List%3CString%3E getShortestPathTo(String sourceLabel, String destLabel) %7B%0A    List%3CString%3E shortestPath = new ArrayList%3CString%3E();%0A    Vertex%3CString%3E sourceVertex = graph.getVertex(sourceLabel);%0A    Vertex%3CString%3E destVertex = graph.getVertex(destLabel);%0A%0A    if (sourceVertex != null && destVertex != null) %7B%0A      getShortestPathTo(sourceVertex, destVertex, shortestPath);%0A    %7D%0A%0A    return shortestPath;%0A  %7D%0A%0A  private void getShortestPathTo(Vertex%3CString%3E sourceVertex, Vertex%3CString%3E destVertex, List%3CString%3E shortestPath) %7B%0A    int i = indexesMap.get(sourceVertex);%0A    int j = indexesMap.get(destVertex);%0A    %0A    if(destVertex == null) %7B%0A      shortestPath.clear();%0A    %7D else if(destVertex.equals(sourceVertex)) %7B%0A      shortestPath.add(sourceVertex.label);%0A    %7D else %7B%0A      shortestPath.add(destVertex.label);%0A      getShortestPathTo(sourceVertex, pathMatrix%5Bi%5D%5Bj%5D, shortestPath);%0A    %7D%0A  %7D
 %0A%7D

Add recursive method to fetchShortestPath