/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package graphs;

/**
 *
 * @author David
 */
public class Floyd
{
    private int[][] m_graph;
    private int[][] m_next;
    private int[][] m_path;

    private static int INFINITY = 9999999;

    public Floyd(int n)
    {
        m_graph = new int[n][n];
        m_next  = new int[n][n];
        m_path  = new int[n][n];

        createSampleGraph();
    }

    public void floyd()
    {
        init();
        int n = m_graph.length;
        for(int k = 0; k < n; ++k)
            for(int v = 0; v < n; ++v)
                for(int w = 0; w < n; ++w)
                    if(m_path[v][k] + m_path[k][w] < m_path[v][w])
                    {
                        m_path[v][w] = m_path[v][k] + m_path[k][w];
                        m_next[v][w] = k;
                    }

    }

    public void print(int source, int end)
    {
        int k = m_next[source][end];
        if(k != -1)
        {
            print(source, k);
            System.out.println(k);
            print(k, end);
        }
    }

    private void init()
    {
        int n = m_graph.length;
        for(int v = 0; v < n; ++v)
            for(int w = 0; w < n; ++w)
            {
                m_path[v][w] = m_graph[v][w];
                m_next[v][w] = -1;
            }
    }

    private void createSampleGraph()
    {
        for(int i = 0; i < m_graph.length; ++i)
            for(int j = 0; j < m_graph.length; ++j)
            {
                if(i == j)
                    m_graph[i][j] = 0;
                else
                    m_graph[i][j] = INFINITY;
            }

        m_graph[0][1] = 10;
        m_graph[0][4] = 100;
        m_graph[0][3] = 30;
        m_graph[1][2] = 50;
        m_graph[2][4] = 10;
        m_graph[3][2] = 20;
        m_graph[3][4] = 60;
    }
}

/*
Gebruik
*/
public class Backtracking {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        Floyd f = new Floyd(5);
        f.floyd();
        f.print(0, 4);

    }
}