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

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

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

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<MyPoint> arrMyPoint = new ArrayList<MyPoint>();
    private ArrayList<MyLine> arrMyLine = new ArrayList<MyLine>();
    private ArrayList<Integer> arrPointResult;
    private ArrayList<Integer> arrPointResultStep;
    private ArrayList<Integer> arrCostResult = new ArrayList<Integer>();
    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<Integer> 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<Integer>();
        // 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<Integer> getArrPointResultStep() {
        return arrPointResultStep;
    }

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

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

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

    public ArrayList<Integer> getArrTempPoint() {
        return arrTempPoint;
    }

    public void setArrTempPoint(ArrayList<Integer> 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<MyPoint> getArrMyPoint() {
        return arrMyPoint;
    }

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

    public ArrayList<MyLine> getArrMyLine() {
        return arrMyLine;
    }

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

    public ArrayList<Integer> getArrPointResult() {
        return arrPointResult;
    }

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

    public ArrayList<Integer> getArrCostResult() {
        return arrCostResult;
    }

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

}
Bạn thấy bài viết này như thế nào?: 
Average: 5.3 (3 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Hướng dẫn sử dụng Organic Groups module trong Drupal 7

Hướng dẫn sử dụng Organic Groups module trong Drupal 7

Organic Groups (OG) is the social networking solution for Drupal.

Hướng dẫn chèn lời bình vào văn bản word

Hướng dẫn chèn lời bình vào văn bản word

Sử dụng các nút trên thanh công cụ Reviewing để xác nhận hay hủy bỏ quá trình Track changes và để xóa các Comments (câu bình luận).

HTC Titan Review: 1st Windows 7 Phone By HTC

HTC Titan Review: 1st Windows 7 Phone By HTC

The HTC titan it is one big smartphone. This huge phone is grabbing eyeballs as this newest Windows device proudly flaunts the 4.7″ screen making the display large and clear.

Tomdesgin.vn

 

Drupal Services