Mô phỏng thuật toán Dijkstra tìm đường đi ngắn nhất bằng java

Chương trình cho phép người dùng vẽ đồ thị một cách nhanh chóng và dễ dàng, các điểm có thể kéo đi kéo lại, xóa, sửa tri phí (trọng số), … hoặc có thể dùng các đồ thị có sẵn trong phần demo. Và khi chạy sẽ hiển thị quá trình đường đi trên cả đồ thị cũng như phần bên dưới Log. Dưới cùng còn có một bảng để mô tả các công việc mà khi làm bằng tay chúng ta cần làm để tìm đường đi ngắn nhất. Chương trình cũng cho phép lưu lại đồ thị, mở đồ thị đã lưu.

Lưu ý: Full source thuật toán Dijkstra bằng Java có link download phía dưới

Xem lại lý thuyết từ link sau

>> Cài đặt chương trình mô phỏng thuật toán Dijkstra bằng Pascal

package nguyenvanquan7826;

import java.util.ArrayList;

public class MyDijkstra {
    private int a[][];
    private int[] len, p;
    private int[][] logLen, logP;
    private boolean[] checkedPointMin; // diem co duong di ngan nhat (da xet)
    private int infinity, size = 0;
    private ArrayList arrMyPoint = new ArrayList();
    private ArrayList arrMyLine = new ArrayList();
    private ArrayList arrPointResult;
    private ArrayList arrPointResultStep;
    private ArrayList arrCostResult = new ArrayList();
    private int beginPoint = 0, endPoint = 0;
    private int numberPointChecked = 0;
    private boolean step = false;
    private boolean stop = false;
    private boolean mapType = false;
    private String path = "";
    private ArrayList arrTempPoint;

    public MyDijkstra() {
    }

    public void input() {
        infinity = 1;
        size = arrMyPoint.size();
        // System.out.println(size);
        a = new int[size][size];
        len = new int[size];
        p = new int[size];
        checkedPointMin = new boolean[size];

        for (int i = 1; i < arrMyLine.size(); i++) {
            a[arrMyLine.get(i).getIndexPointA()][arrMyLine.get(i)
                    .getIndexPointB()] = arrMyLine.get(i).getCost();
            if (!mapType) {
                a[arrMyLine.get(i).getIndexPointB()][arrMyLine.get(i)
                        .getIndexPointA()] = arrMyLine.get(i).getCost();
            }
            infinity += arrMyLine.get(i).getCost();
        }
    }

    public void processInput() {
        for (int i = 1; i < size; i++) {
            for (int j = 1; j < size; j++) {
                if (a[i][j] == 0 && i != j) {
                    a[i][j] = infinity;
                }
            }
        }
    }

    public String outputMatrix() {
        // System.out.printf(mapType + "\n");
        for (int i = 1; i < size; i++) {
            for (int j = 1; j < size; j++) {
                if (a[i][j] == infinity) {
                    System.out.printf("%5s", "∞");
                } else {
                    System.out.printf("%5d", a[i][j]);
                }
            }
        }
        return "";
    }

    private void initValue() {
        logLen = new int[size][size];
        logP = new int[size][size];
        // processInput();
        for (int i = 1; i < size; i++) {
            len[i] = infinity;
            checkedPointMin[i] = false;
            p[i] = 0;
        }
        logLen[0] = len;
        logP[0] = p;
        len[beginPoint] = 0;
    }

    public int dijkstra() {
        initValue();
        int i = 1, k = 0;
        // for (int k = 1; k < size; k++) {
        while (checkContinue(k)) {
            for (i = 1; i < size; i++)
                if (!checkedPointMin[i] && len[i] < infinity)
                    break;
            if (i >= size)
                break;
            for (int j = 1; j < size; j++)
                if (!checkedPointMin[j] && len[i] > len[j])
                    i = j;

            checkedPointMin[i] = true;
            for (int j = 1; j < size; j++) {
                if (!checkedPointMin[j] && len[i] + a[i][j] < len[j]) {
                    len[j] = len[i] + a[i][j];
                    p[j] = i;

                }
                logLen[k][j] = len[j];
                logP[k][j] = p[j];
            }
            k++;
        }
        if (endPoint == -1) { // endPoint = -1 -> beginPoint to all Point
            numberPointChecked = arrMyPoint.size();
            return 0;
        }
        numberPointChecked = k;
        return len[endPoint];
    }

    public int dijkstraStep(int step) {
        initValue();
        int i = 0, k = 0;
        arrPointResultStep = new ArrayList();
        // while (!checkPointMin[end] && k < step) {
        while (checkContinueStep(step, k)) {
            for (i = 1; i < size; i++)
                if (!checkedPointMin[i] && len[i] < infinity)
                    break;
            if (i >= size) {
                stop = true;
                break;
            }
            for (int j = 1; j < size; j++)
                if (!checkedPointMin[j] && len[i] > len[j])
                    i = j;

            checkedPointMin[i] = true;
            for (int j = 1; j < size; j++) {
                if (!checkedPointMin[j] && len[i] + a[i][j] < len[j]) {
                    len[j] = len[i] + a[i][j];
                    p[j] = i;
                }
                logLen[k][j] = len[j];
                logP[k][j] = p[j];
            }
            arrPointResultStep.add(i);
            k++;
        }
        if (endPoint == -1) {
            numberPointChecked = arrMyPoint.size();
            return 0;
        }
        numberPointChecked = k;
        return len[endPoint];
    }

    private boolean checkContinueStep(int step, int k) {
        if (endPoint != -1) {
            return (!checkedPointMin[endPoint] && k < step);
        }
        return (k < arrMyPoint.size() - 1 && k < step);
    }

    private boolean checkContinue(int k) {
        if (endPoint != -1) {
            return (!checkedPointMin[endPoint]);
        }
        return (k < arrMyPoint.size() - 1);
    }

    public String tracePath() {
        path = "";
        if (endPoint > 0 && len[endPoint] < infinity) {
            int i = endPoint;
            while (i != beginPoint) {
                path = " --> " + i + path;
                i = p[i];
            }
            path = "The cost from " + beginPoint + " to " + endPoint + " is "
                    + len[endPoint] + "\t" + "Path : " + i + path;
        } else if (endPoint == -1) {
            for (int i = arrMyPoint.size() - 1; i >= 1; i--) {
                int j = i;
                if (len[i] < infinity) {
                    while (j != beginPoint) {
                        path = " --> " + j + path;
                        j = p[j];
                    }
                    path = "The cost from " + beginPoint + " to " + i + " is "
                            + len[i] + "\t" + "Path : " + j + path;

                } else {
                    path = "Can't go from " + beginPoint + " to " + i + path;
                }
                if (i > 1) {
                    path = "\n" + path;
                }
            }
        } else {
            path = "Can't go from " + beginPoint + " to " + endPoint;
        }
        return path;
    }

    public String tracePathStep() {
        path = "";
        if (endPoint > 0) {
            int i = arrPointResultStep.get(arrPointResultStep.size() - 1);
            int j = i;
            while (j != beginPoint) {
                path = " --> " + j + path;
                j = p[j];
            }
            path = "The cost from " + beginPoint + " to " + i + " is " + len[i]
                    + "\t" + "Path : " + j + path;

            if (stop) {
                path = "Can't go from " + beginPoint + " to " + endPoint;
            }
        } else if (endPoint == -1) {
            for (int i = arrPointResultStep.size() - 1; i >= 0; i--) {
                int e = arrPointResultStep.get(i);
                int j = e;
                while (j != beginPoint) {
                    path = " --> " + j + path;
                    j = p[j];
                }
                path = "The cost from " + beginPoint + " to " + e + " is "
                        + len[e] + "\t" + "Path : " + j + path;

                if (stop) {
                    path = "Can't go from " + beginPoint + " to " + endPoint;
                }
                if (i > 0) {
                    path = "\n" + path;
                }
            }

        }

        return path;
    }

    // public void show() {
    // input();
    // processInput();
    // outputMatrix();
    // // trace();
    // }
    public int getNumberPointChecked() {
        return numberPointChecked;
    }

    public void setNumberPointChecked(int numberPointChecked) {
        this.numberPointChecked = numberPointChecked;
    }

    public int[][] getLogLen() {
        return logLen;
    }

    public void setLogLen(int[][] logLen) {
        this.logLen = logLen;
    }

    public int[][] getLogP() {
        return logP;
    }

    public void setLogP(int[][] logP) {
        this.logP = logP;
    }

    public boolean isMapType() {
        return mapType;
    }

    public void setMapType(boolean mapType) {
        this.mapType = mapType;
    }

    public boolean[] getCheckedPointMin() {
        return checkedPointMin;
    }

    public void setCheckedPointMin(boolean[] checkedPointMin) {
        this.checkedPointMin = checkedPointMin;
    }

    public ArrayList getArrPointResultStep() {
        return arrPointResultStep;
    }

    public void setArrPointResultStep(ArrayList arrPointResultStep) {
        this.arrPointResultStep = arrPointResultStep;
    }

    public int[] getP() {
        return p;
    }

    public void setP(int[] p) {
        this.p = p;
    }

    public ArrayList getArrTempPoint() {
        return arrTempPoint;
    }

    public void setArrTempPoint(ArrayList arrTempPoint) {
        this.arrTempPoint = arrTempPoint;
    }

    public boolean isStop() {
        return stop;
    }

    public void setStop(boolean stop) {
        this.stop = stop;
    }

    public boolean isStep() {
        return step;
    }

    public void setStep(boolean step) {
        this.step = step;
    }

    public int getInfinity() {
        return infinity;
    }

    public void setInfinity(int infinity) {
        this.infinity = infinity;
    }

    public int[] getLen() {
        return len;
    }

    public void setLen(int[] len) {
        this.len = len;
    }

    public int[][] getA() {
        return a;
    }

    public void setA(int[][] a) {
        this.a = a;
    }

    public int getBeginPoint() {
        return beginPoint;
    }

    public void setBeginPoint(int beginPoint) {
        this.beginPoint = beginPoint;
    }

    public int getEndPoint() {
        return endPoint;
    }

    public void setEndPoint(int endPoint) {
        this.endPoint = endPoint;
    }

    public ArrayList getArrMyPoint() {
        return arrMyPoint;
    }

    public void setArrMyPoint(ArrayList arrMyPoint) {
        this.arrMyPoint = arrMyPoint;
    }

    public ArrayList getArrMyLine() {
        return arrMyLine;
    }

    public void setArrMyLine(ArrayList arrMyLine) {
        this.arrMyLine = arrMyLine;
    }

    public ArrayList getArrPointResult() {
        return arrPointResult;
    }

    public void setArrPointResult(ArrayList arrPointResult) {
        this.arrPointResult = arrPointResult;
    }

    public ArrayList getArrCostResult() {
        return arrCostResult;
    }

    public void setArrCostResult(ArrayList arrCostResult) {
        this.arrCostResult = arrCostResult;
    }

}

Source: https://vh2.com.vn
Category : Tin Học