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 Integrating multisite Drupal với Apache Solr

Hướng dẫn Integrating multisite Drupal với Apache Solr

Using this approach, you create an unique Solr core (N.B. a single Solr application can contain 0 or more cores) per site and either:

Bắt đầu làm quen với Big Data - What and Why

Bắt đầu làm quen với Big Data - What and Why

Chào các bạn, mình là Hải, lĩnh vực chuyên môn của mình là xây dựng các ứng dụng trên nền tảng Web (Web application development).

Nội dung, keyword có dấu hay không có dấu trong SEO

Nội dung, keyword có dấu hay không có dấu trong SEO

SEO nội dung, keyword có dấu hay không có dấu khi thiết kế web là chủ đề mà các SEOer bàn tán khá nhiều trong những buổi Off của SEOer.

Công ty diệt chuột T&C

 

Diet con trung