다익스트라(Dijkstra Algorithm)

class GraphDijkstra {

    final int INFINITY = 60000;

    private int[][] adjMat;
    private Vertex[] vertices;
    private int[] distance;

    private int numVertices;

    public GraphDijkstra(int max) {
        adjMat = new int[max][max];
        vertices = new Vertex[max];
        distance = new int[max];

        numVertices = 0;

        for (int i = 0; i < max; i++) {
            distance[i] = INFINITY;
            for (int j = 0; j < max; j++)
                adjMat[i][j] = INFINITY;
        }
    }

    public void addVertex(Vertex v) {
        v.setId(numVertices);
        vertices[numVertices] = v;
        numVertices += 1;
    }

    public void addEdge(Vertex src, Vertex dst, int w) {
        adjMat[src.getId()][dst.getId()] = w;
        adjMat[dst.getId()][src.getId()] = w;
    }

    public Vertex getMinVertex() {
        Vertex v = null;
        int temDistance = INFINITY;

        for (int i = 0; i < numVertices; i++) {
            //고정되어 있지 않은 꼭지점 중에서 가장 작은 가중치로 연결된 Vertex을 찾는다
            if (!vertices[i].isFixed() && distance[i] < temDistance) {
                temDistance = distance[i];
                v = vertices[i];
            }
        }
        return v;
    }

    public void updateDistance(Vertex v) {
        int tmpDistance;
        for (int i = 0; i < numVertices; i++) {
            if (adjMat[v.getId()][i] < INFINITY) {
                //자기와 연결된 꼭지점에 대해서 자기를 지나는 경로의 거리를 계산
                tmpDistance = distance[v.getId()] + adjMat[v.getId()][i];
                if (tmpDistance < distance[i]) {
                    //거리가 더 짧은 경우 정보를 갱신
                    distance[i] = tmpDistance;
                    vertices[i].prev = v;
                }
            }
        }
    }

    public void SPF(Vertex start) {
        Vertex v;
        distance[start.getId()] = 0;
        v = start;

        do {
            v.setFixed();
            updateDistance(v);
            v = getMinVertex();
        } while (v != null);

        for (int i = 0; i < numVertices; i++) {
            String result[] = new String[numVertices];

            int count = 0;
            v = vertices[i];

            while (v != null) {
                result[count] = v.label;
                count++;
                v = v.prev;
            }
            String log = new String();
            for (int j = count - 1; j >= 0; j--) {
                log += result[j];
                if (j > 0)
                    log += "->";
            }
            Log.i("kjw", log);
        }
    }

    static public class Vertex {
        private String label;
        private int id;
        private boolean isFix;

        public Vertex prev;

        public Vertex(String label) {
            this.label = label;
            isFix = false;
            id = -1;
            prev = null;
        }

        public void setId(int id) {
            this.id = id;
        }

        public int getId() {
            return id;
        }

        public void setFixed() {
            this.isFix = true;
        }

        public boolean isFixed() {
            return isFix;
        }
    }
}