久操精品视频在线观看,久久不卡精品伊人,大香蕉零零后妹子网

算法應(yīng)用

指定一個起點，得到該起點到圖的其他所有節(jié)點的最短路徑

核心思想

Dijkstra算法是一種動態(tài)規(guī)劃算法，核心思想是找出指定起點到某個節(jié)點的最短路徑，就要先找出到達該節(jié)點的前一個節(jié)點的最短路徑
執(zhí)行過程要記錄指定起點到其余節(jié)點最短路徑的路徑權(quán)值以及當(dāng)前最短路徑終點的前驅(qū)節(jié)點，并可能隨時更新

算法思路

從指定起點開始，找出所有鄰接節(jié)點，更新起點到鄰接節(jié)點路徑權(quán)值和記錄的前驅(qū)節(jié)點，從中選出路徑權(quán)值最小的一個節(jié)點，作為下一輪的起點
比如起點是B，B的所有鄰接情況有，B-7-A，B-1-C，可以看出B到C是最短的，這里就先選出C為下一輪的起點
從次輪起點開始，重復(fù)第一輪的操作
每一輪更新記錄的路徑權(quán)值，是把 "記錄得原始起點到該目標(biāo)節(jié)點的路徑總權(quán)值" 與 "記錄中原始起點到本輪起點的路徑權(quán)值 + 本輪起點到鄰接節(jié)點的權(quán)值" 比較，如果后者比較大，說明之前記錄的路徑不是最優(yōu)選擇
接著上述例子，B-7-A是原先記錄的B到A的最短路徑，假如第二輪起點C，找到路徑B-1-C-3-A，可以看到B到A總權(quán)值只有4，則把記錄的B到達A的最短路徑權(quán)值從7修改為4，并把A的前驅(qū)從B改成C
更新了權(quán)值的同時要記得更新路徑終點的前驅(qū)節(jié)點
每一輪都將此輪的起點設(shè)置為已訪問，并且尋找鄰接節(jié)點時也要跳過那些已訪問的
所有節(jié)點都"已訪問"時結(jié)束

注意

一個節(jié)點一旦被指定為下一輪的起點，也就是"已訪問"，則該節(jié)點的最短路徑以及前驅(qū)節(jié)點已經(jīng)找到
每一輪選出的下一輪的起點, 不可能再找出另外的路徑使得起點到達選出的點的路徑權(quán)值更小，比如從A到D權(quán)值3, 假定D節(jié)點就是A到所有節(jié)點中路徑最短的，假如A能通過另外的節(jié)點到達D并且路徑更短，比如A-1-E-1-D權(quán)值為2, 則這一輪取出的節(jié)點將是E而不是D

算法實現(xiàn)

用這個例子

給定的圖

完整代碼

小伙伴們可以先復(fù)制完全代碼粘貼到IDE上，然后再看下面的完整步驟

enum Status {  // 節(jié)點對象的狀態(tài)
    // 未被發(fā)現(xiàn), 已被遍歷
    UNDISCOVERD, VISITED
}
public class Graph<T> {
    private int N; // N個節(jié)點
    public int[][] matrix;  // 鄰接矩陣
    private Status[] statuses;  // 保存每個節(jié)點的狀態(tài)
    private T[] datas;  // 保存每個節(jié)點的數(shù)據(jù)
    public Graph(int N) {
        this.N = N;
        matrix = new int[N][N];
        statuses = new Status[N];
        datas = (T[]) new Object[N];  // 泛型數(shù)組實例化
        initStatuses();
    }

    /**
     * 用傳進來的矩陣初始化圖的鄰接矩陣
     *
     * @param matrix 傳進來用于初始化鄰接矩陣的矩陣
     * @return void
     */
    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }


    /**
     * 使圖變成無向圖(把鄰接矩陣鏡像化)
     *
     * @return void
     */
    public void makeUndirected() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] > 0 && matrix[i][j] != matrix[j][i]) {
                    matrix[j][i] = matrix[i][j];
                }
            }
        }
    }

    public void setDatas(T[] datas) {
        this.datas = datas;
    }

    /**
     * 初始化狀態(tài)數(shù)組
     *
     * @return void
     */
    public void initStatuses() {
        for (int i = 0; i < N; i++) {
            statuses[i] = Status.UNDISCOVERD;
        }
    }

    /**
     * 鄰接矩陣保存的信息是從一個節(jié)點指向另一個節(jié)點的信息
     *
     * @param from   從這個節(jié)點
     * @param to     指向這個節(jié)點
     * @param weight 路徑權(quán)重
     * @return void
     */
    public void setMatrix(int from, int to, int weight) {
        matrix[from][to] = weight;
    }

    /**
     * 最短路徑-迪杰斯特拉算法(找出某個點到其他所有點的最短路徑)
     *
     * @param index 指定某個點
     * @return void
     */
    public void DijkstraPath(int index) {
        // 每一輪選出的路徑權(quán)值最小的節(jié)點, 則不可能再找出另外的路徑權(quán)值更小
        // 比如從A到D是2, 則這一輪取出D節(jié)點, 假如有A能通過另外的節(jié)點到達D并且更短,
        // 比如A-1-E-1-D, 則上一輪取出的節(jié)點將是E而不是D
        // 數(shù)組存放該點到各個點的路徑權(quán)值
        int[] weights = new int[N];
        // 將每個默認權(quán)值設(shè)置為整型最大值
        for (int i = 0; i < N; i++) {
            weights[i] = Integer.MAX_VALUE;
        }
        // 數(shù)組記錄指定節(jié)點到每個節(jié)點的最短路徑中, 終點節(jié)點的前驅(qū)節(jié)點
        // 動態(tài)規(guī)劃: 找到到達某個節(jié)點的最短路徑, 先找到到達他的上一個節(jié)點的最短路徑
        int[] prevs = new int[N];
        prevs[index] = -1;  // 負數(shù)表示該點沒有前驅(qū)
        // 循環(huán)所用的輔助索引
        int from = index;
        // 只要不是全部被遍歷
        while (!isAllVisited()) {
            // 將這個節(jié)點設(shè)置為已訪問
            statuses[from] = Status.VISITED;
            // 查看鄰接矩陣中與指定節(jié)點鄰接的節(jié)點
            for (int i = 0; i < N; i++) {
                // 可能的新路徑權(quán)值: 從最開始的指定起點到本輪起點到該節(jié)點的路徑權(quán)值總和
                int newWeight;
                if (weights[from] == Integer.MAX_VALUE) {
                    newWeight = matrix[from][i];
                } else {
                    newWeight = weights[from] + matrix[from][i];
                }
                // 如果節(jié)點未訪問, 且是鄰接節(jié)點
                if (statuses[i] == Status.UNDISCOVERD && matrix[from][i] > 0
                        // 并且如果小于weights中記錄的該節(jié)點原來的路徑權(quán)值
                        && newWeight < weights[i]) {
                    // 則更新該節(jié)點的最小路徑值, 更新該節(jié)點的前驅(qū)為本輪起點
                    weights[i] = newWeight;
                    prevs[i] = from;
                }
            }
            // 下輪起點from設(shè)置為: weights數(shù)組中數(shù)值最小的并且未訪問的節(jié)點
            from = indexOfMin(weights);
        }
        // 輸出結(jié)果
        System.out.println("指定起點為:" + datas[index]);
        for (int i = 0; i < N; i++) {
            if (i != index) {  // 除去最開始指定的起點
                List<Integer> nodesInPath = allPrevs(prevs, i);
                System.out.print("起點" + datas[index] + "到" + datas[i] + "點的最短路徑是: " + datas[index]);
                for (int j :nodesInPath) {
                    System.out.print("-" + matrix[prevs[j]][j] + "-" + datas[j]);
                }
                System.out.println("-" + matrix[prevs[i]][i] + "-" + datas[i] + ", 路徑權(quán)值總和為: " + weights[i]);
            }
        }
    }

    /**
     * 指定節(jié)點, 按路徑順序返回該節(jié)點的所有前驅(qū)節(jié)點
     *
     * @param prevs 記錄前驅(qū)節(jié)點的數(shù)組
     * @param index 指定節(jié)點
     * @return java.util.List<java.lang.Integer>
     */
    private List<Integer> allPrevs(int[] prevs, int index) {
        // 記錄指定節(jié)點到達指定起點的最短路徑沿途的節(jié)點
        Stack<Integer> prevStack = new Stack<>();
        int prev = prevs[index];
        // 前面設(shè)置的算法最開始指定的起點的前驅(qū)索引為-1在這里起作用
        // 只要前驅(qū)的前驅(qū)索引不為最開始指定的起點
        while (prevs[prev] != -1) {
            // 把前驅(qū)索引加入棧
            prevStack.add(prev);
            // 下次循環(huán)要檢查此次循環(huán)前驅(qū)節(jié)點的前驅(qū)節(jié)點, 所以更新變量
            prev = prevs[prev];
        }

        // 方便遍歷, 倒序輸出
        List<Integer> result = new ArrayList<>();
        while (!prevStack.isEmpty()) {
            result.add(prevStack.pop());
        }
        return result;
    }

    /**
     * 檢查是否全部被遍歷(只要有一個是未被遍歷返回false)
     *
     * @return boolean
     */
    private boolean isAllVisited() {
        for (Status status : statuses) {
            if (status == Status.UNDISCOVERD) {
                return false;
            }
        }
        return true;
    }

    /**
     * 找到數(shù)組中最小的值的索引
     *
     * @return int
     */
    private int indexOfMin(int[] nums) {
        List<Integer> remain = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            if (statuses[i] == Status.UNDISCOVERD) {
                remain.add(i);
            }
        }
        if (remain.size() == 0) {
            return 0;  // 這里返回什么都行, 因為所有節(jié)點會在下一循環(huán)全部設(shè)置為已訪問, 從而循環(huán)內(nèi)無任何操作
        }
        int minIndex = remain.get(0);
        for (int j : remain) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        return minIndex;
    }

    public static void main(String[] args) {
        Graph<String> graph = new Graph<>(7);
        graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F", "G"});
        int[][] matrix = {
                {0, 7, 3, 2, 2, 0, 0},
                {0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 4, 3, 0},
                {0, 0, 0, 0, 1, 10, 2},
                {0, 0, 0, 0, 0, 4, 2},
                {0, 0, 0, 0, 0, 0, 7},
                {0, 0, 0, 0, 0, 0, 0}};
        graph.setMatrix(matrix);
        graph.makeUndirected();
        for (int i = 0; i < 7; i++) {
            graph.initStatuses();
            graph.DijkstraPath(i);
        }
    }
}

圖的實現(xiàn)

此實現(xiàn)方法沒有節(jié)點類
采用鄰接矩陣，并用頂點索引代表頂點
鄰接矩陣int[][] matrix
- matrix[i][j]表示從索引i的節(jié)點指向索引j的節(jié)點的權(quán)值
- 權(quán)值為0表示兩點不連接或者自身與自身不連接
使用枚舉來定義節(jié)點的狀態(tài)enum Status { UNDISCOVERD, VISITED }
枚舉數(shù)組Status[] statuses記錄每個節(jié)點的狀態(tài)

enum Status {  // 節(jié)點對象的狀態(tài)
    // 未被發(fā)現(xiàn), 已被遍歷
    UNDISCOVERD, VISITED
}
public class Graph<T> {
    private int N; // N個節(jié)點
    public int[][] matrix;  // 鄰接矩陣
    private Status[] statuses;  // 保存每個節(jié)點的狀態(tài)
    private T[] datas;  // 保存每個節(jié)點的數(shù)據(jù)
}

具體過程

算法主體方法void DijkstraPath(int index)，index就是指定原始起點
int[] weights存放指定起點到各個點的路徑權(quán)值(初始值設(shè)定為整型最大值，動態(tài)更新)
int[] prevs記錄指定起點到每個節(jié)點的最短路徑中, 終點節(jié)點的前驅(qū)節(jié)點(將起點的前驅(qū)索引設(shè)置為負數(shù)，表示沒有前驅(qū))
int from每一輪指定的起點索引(循環(huán)的輔助索引)，初始化為原始起點索引

    public void DijkstraPath(int index) {
        // 數(shù)組存放該點到各個點的路徑權(quán)值
        int[] weights = new int[N];
        // 將每個默認權(quán)值設(shè)置為整型最大值
        for (int i = 0; i < N; i++) {
            weights[i] = Integer.MAX_VALUE;
        }
        // 數(shù)組記錄指定節(jié)點到每個節(jié)點的最短路徑中, 終點節(jié)點的前驅(qū)節(jié)點
        // 動態(tài)規(guī)劃: 找到到達某個節(jié)點的最短路徑, 先找到到達他的上一個節(jié)點的最短路徑
        int[] prevs = new int[N];
        prevs[index] = -1;  // 負數(shù)表示該點沒有前驅(qū)
        // 循環(huán)所用的輔助索引
        int from = index;

補充三個方法
1. boolean isAllVisited()判斷是否所有節(jié)點都是"已訪問"，檢查所有節(jié)點的狀態(tài)，只要有一個是未被訪問UNDISCOVERD，就返回false
2. int indexOfMin(int[] nums)找出給定數(shù)組中最小值的索引，過濾掉已訪問的節(jié)點，把未訪問的節(jié)點索引加入集合List<Integer> remain，remain.add(i)用于每輪循環(huán)結(jié)束前，找出未被訪問且在weights中記錄的路徑權(quán)值最小的節(jié)點的索引
3. List<Integer> allPrevs(int[] prevs, int index)從記錄所有節(jié)點的前驅(qū)索引的數(shù)組prevs找出原始節(jié)點到指定索引index的節(jié)點的最短路徑上除了原始起點和終點外的所有中間節(jié)點，并記錄在棧Stack<Integer> prevStack中，最后依次彈出存到List<Integer> result中，用于最后輸出查看結(jié)果
  用prev作為輔助變量，逐層往上尋找前驅(qū)，只要當(dāng)前節(jié)點前驅(qū)索引不是-1 while (prevs[prev] != -1)也就是當(dāng)前節(jié)點不是原始起點(上面已經(jīng)把原始起點的前驅(qū)索引設(shè)置為-1)，就把當(dāng)前節(jié)點加入棧prevStack.add(prev)，最后只要棧不空!prevStack.isEmpty()，就彈出棧頂加入集合result.add(prevStack.pop())

    /**
     * 檢查是否全部被遍歷(只要有一個是未被遍歷返回false)
     *
     * @return boolean
     */
    private boolean isAllVisited() {
        for (Status status : statuses) {
            if (status == Status.UNDISCOVERD) {
                return false;
            }
        }
        return true;
    }

    /**
     * 找到數(shù)組中最小的值的索引
     *
     * @return int
     */
    private int indexOfMin(int[] nums) {
        // 記錄剩余的未訪問的節(jié)點
        List<Integer> remain = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            if (statuses[i] == Status.UNDISCOVERD) {
                remain.add(i);
            }
        }
        if (remain.size() == 0) {
            return 0;  // 這里返回什么都行, 因為所有節(jié)點會在下一循環(huán)全部設(shè)置為已訪問, 從而循環(huán)內(nèi)無任何操作
        }
        int minIndex = remain.get(0);
        for (int j : remain) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        return minIndex;
    }

    /**
     * 指定節(jié)點, 按路徑順序返回該節(jié)點的所有前驅(qū)節(jié)點
     *
     * @param prevs 記錄前驅(qū)節(jié)點的數(shù)組
     * @param index 指定節(jié)點
     * @return java.util.List<java.lang.Integer>
     */
    private List<Integer> allPrevs(int[] prevs, int index) {
        // 記錄指定節(jié)點到達指定起點的最短路徑沿途的節(jié)點
        Stack<Integer> prevStack = new Stack<>();
        int prev = prevs[index];
        // 前面設(shè)置的算法最開始指定的起點的前驅(qū)索引為-1在這里起作用
        // 只要前驅(qū)的前驅(qū)索引不為最開始指定的起點
        while (prevs[prev] != -1) {
            // 把前驅(qū)索引加入棧
            prevStack.add(prev);
            // 下次循環(huán)要檢查此次循環(huán)前驅(qū)節(jié)點的前驅(qū)節(jié)點, 所以更新變量
            prev = prevs[prev];
        }

        // 方便遍歷, 倒序輸出
        List<Integer> result = new ArrayList<>();
        while (!prevStack.isEmpty()) {
            result.add(prevStack.pop());
        }
        return result;
    }

只要不是所有節(jié)點都是"已訪問"while (!isAllVisited())，則循環(huán)執(zhí)行
1. 將每一輪的起點設(shè)置為"已訪問"VISITED
2. 查看鄰接矩陣中與指定節(jié)點鄰接的節(jié)點
  1. int newWeight表示可能的新路徑權(quán)值: 從最開始的指定起點到本輪起點到該節(jié)點的路徑權(quán)值總和
    由于最開始weights數(shù)組所有值初始化為整型最大值，所以判斷if (weights[from] == Integer.MAX_VALUE)該本輪起點在weights中記錄的權(quán)值是不是整型最大值，是就說明這個節(jié)點第一次被查找(這種情況只在第一輪循環(huán)中會出現(xiàn))，newWeight = matrix[from][i]則可能的新權(quán)值直接設(shè)置為起點到該鄰接節(jié)點的邊權(quán)值，否則設(shè)置為newWeight = weights[from] + matrix[from][i]"原始起點到本輪起點的路徑權(quán)值 + 本輪起點到該鄰接節(jié)點的邊權(quán)值"，
  2. if (statuses[i] == Status.UNDISCOVERD && matrix[from][i] > 0 && newWeight < weights[i])如果該節(jié)點未被訪問，且是鄰接節(jié)點，并且如果newWeight小于weights中記錄的原始起點到該節(jié)點的路徑權(quán)值，則更新該節(jié)點的最小路徑值, 更新該節(jié)點的前驅(qū)為本輪起點weights[i] = newWeight，prevs[i] = from
  3. from = indexOfMin(weights)設(shè)定下一輪的起點為未被訪問且是weights數(shù)組中記錄的路徑權(quán)值中最小的一個節(jié)點

        // 循環(huán)所用的輔助索引
        int from = index;
        // 只要不是全部被遍歷
        while (!isAllVisited()) {
            // 將這個節(jié)點設(shè)置為已訪問
            statuses[from] = Status.VISITED;
            // 查看鄰接矩陣中與指定節(jié)點鄰接的節(jié)點
            for (int i = 0; i < N; i++) {
                // 可能的新路徑權(quán)值: 從最開始的指定起點到本輪起點到該節(jié)點的路徑權(quán)值總和
                int newWeight;
                if (weights[from] == Integer.MAX_VALUE) {
                    newWeight = matrix[from][i];
                } else {
                    newWeight = weights[from] + matrix[from][i];
                }
                // 如果節(jié)點未訪問, 且是鄰接節(jié)點
                if (statuses[i] == Status.UNDISCOVERD && matrix[from][i] > 0
                        // 并且如果小于weights中記錄的該節(jié)點原來的路徑權(quán)值
                        && newWeight < weights[i]) {
                    // 則更新該節(jié)點的最小路徑值, 更新該節(jié)點的前驅(qū)為本輪起點
                    weights[i] = newWeight;
                    prevs[i] = from;
                }
            }
            // 下輪起點from設(shè)置為: weights數(shù)組中數(shù)值最小的并且未訪問的節(jié)點
            from = indexOfMin(weights);
        }

整個while循環(huán)結(jié)束之后，就可以檢查輸出結(jié)果
- datas[index]是輸出起點保存的數(shù)據(jù)，datas數(shù)組是圖類的成員變量，保存每個節(jié)點儲存的數(shù)據(jù)，比如我用的是每個節(jié)點保存一個字母，方便觀察
- 遍歷每個節(jié)點，得到每個節(jié)點與起點的路徑上的所有中間節(jié)點List<Integer> nodesInPath = allPrevs(prevs, i)，再遍歷nodesInPath依次輸出邊的權(quán)值matrix[prevs[j]][j](這里prevs[j]和j可以倒過來，因為用的是無向圖)，輸出節(jié)點數(shù)據(jù)datas[j]最后在跟上總路徑權(quán)值weights[i]

        System.out.println("指定起點為:" + datas[index]);
        for (int i = 0; i < N; i++) {
            if (i != index) {  // 除去最開始指定的起點
                List<Integer> nodesInPath = allPrevs(prevs, i);
                System.out.print("起點" + datas[index] + "到" + datas[i] + "點的最短路徑是: " + datas[index]);
                for (int j :nodesInPath) {
                    System.out.print("-" + matrix[prevs[j]][j] + "-" + datas[j]);
                }
                System.out.println("-" + matrix[prevs[i]][i] + "-" + datas[i] + ", 路徑權(quán)值總和為: " + weights[i]);
            }
        }

測試

graph7個節(jié)點一次保存7個字母"ABCDEFG"
鄰接矩陣int[][] matrix所表示的圖請看下方圖片
graph.makeUndirected()是把圖變成無向圖，也就是使得鄰接矩陣沿左對角線對稱
查看分別以每個節(jié)點為起點時，到其他節(jié)點的最短路徑的情況，graph.initStatuses()是把所有節(jié)點的狀態(tài)設(shè)置為未訪問，graph.DijkstraPath(i)就是算法主體的方法

    public static void main(String[] args) {
        Graph<String> graph = new Graph<>(7);
        graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F", "G"});
        int[][] matrix = {
                {0, 7, 3, 2, 2, 0, 0},
                {0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 4, 3, 0},
                {0, 0, 0, 0, 1, 10, 2},
                {0, 0, 0, 0, 0, 4, 2},
                {0, 0, 0, 0, 0, 0, 7},
                {0, 0, 0, 0, 0, 0, 0}};
        graph.setMatrix(matrix);
        graph.makeUndirected();
        for (int i = 0; i < 7; i++) {
            graph.initStatuses();
            graph.DijkstraPath(i);
        }
    }

輸出結(jié)果

指定起點為:A
起點A到B點的最短路徑是: A-3-C-1-B, 路徑權(quán)值總和為: 4
起點A到C點的最短路徑是: A-3-C, 路徑權(quán)值總和為: 3
起點A到D點的最短路徑是: A-2-D, 路徑權(quán)值總和為: 2
起點A到E點的最短路徑是: A-2-E, 路徑權(quán)值總和為: 2
起點A到F點的最短路徑是: A-2-E-4-F, 路徑權(quán)值總和為: 6
起點A到G點的最短路徑是: A-2-D-2-G, 路徑權(quán)值總和為: 4

指定起點為:B
起點B到A點的最短路徑是: B-1-C-3-A, 路徑權(quán)值總和為: 4
起點B到C點的最短路徑是: B-1-C, 路徑權(quán)值總和為: 1
起點B到D點的最短路徑是: B-1-C-3-A-2-D, 路徑權(quán)值總和為: 6
起點B到E點的最短路徑是: B-1-C-4-E, 路徑權(quán)值總和為: 5
起點B到F點的最短路徑是: B-1-C-3-F, 路徑權(quán)值總和為: 4
起點B到G點的最短路徑是: B-1-C-4-E-2-G, 路徑權(quán)值總和為: 7

指定起點為:C
起點C到A點的最短路徑是: C-3-A, 路徑權(quán)值總和為: 3
起點C到B點的最短路徑是: C-1-B, 路徑權(quán)值總和為: 1
起點C到D點的最短路徑是: C-3-A-2-D, 路徑權(quán)值總和為: 5
起點C到E點的最短路徑是: C-4-E, 路徑權(quán)值總和為: 4
起點C到F點的最短路徑是: C-3-F, 路徑權(quán)值總和為: 3
起點C到G點的最短路徑是: C-4-E-2-G, 路徑權(quán)值總和為: 6

指定起點為:D
起點D到A點的最短路徑是: D-2-A, 路徑權(quán)值總和為: 2
起點D到B點的最短路徑是: D-1-E-4-C-1-B, 路徑權(quán)值總和為: 6
起點D到C點的最短路徑是: D-1-E-4-C, 路徑權(quán)值總和為: 5
起點D到E點的最短路徑是: D-1-E, 路徑權(quán)值總和為: 1
起點D到F點的最短路徑是: D-1-E-4-F, 路徑權(quán)值總和為: 5
起點D到G點的最短路徑是: D-2-G, 路徑權(quán)值總和為: 2

指定起點為:E
起點E到A點的最短路徑是: E-2-A, 路徑權(quán)值總和為: 2
起點E到B點的最短路徑是: E-4-C-1-B, 路徑權(quán)值總和為: 5
起點E到C點的最短路徑是: E-4-C, 路徑權(quán)值總和為: 4
起點E到D點的最短路徑是: E-1-D, 路徑權(quán)值總和為: 1
起點E到F點的最短路徑是: E-4-F, 路徑權(quán)值總和為: 4
起點E到G點的最短路徑是: E-2-G, 路徑權(quán)值總和為: 2

指定起點為:F
起點F到A點的最短路徑是: F-3-C-3-A, 路徑權(quán)值總和為: 6
起點F到B點的最短路徑是: F-3-C-1-B, 路徑權(quán)值總和為: 4
起點F到C點的最短路徑是: F-3-C, 路徑權(quán)值總和為: 3
起點F到D點的最短路徑是: F-4-E-1-D, 路徑權(quán)值總和為: 5
起點F到E點的最短路徑是: F-4-E, 路徑權(quán)值總和為: 4
起點F到G點的最短路徑是: F-4-E-2-G, 路徑權(quán)值總和為: 6

指定起點為:G
起點G到A點的最短路徑是: G-2-D-2-A, 路徑權(quán)值總和為: 4
起點G到B點的最短路徑是: G-2-E-4-C-1-B, 路徑權(quán)值總和為: 7
起點G到C點的最短路徑是: G-2-E-4-C, 路徑權(quán)值總和為: 6
起點G到D點的最短路徑是: G-2-D, 路徑權(quán)值總和為: 2
起點G到E點的最短路徑是: G-2-E, 路徑權(quán)值總和為: 2
起點G到F點的最短路徑是: G-2-E-4-F, 路徑權(quán)值總和為: 6

希望我寫明白了
如果你看完之后，知道如何實現(xiàn)這個算法，我會很開心
覺得我寫的還行的話，麻煩給老弟點個贊

這里再不要臉的推一下自己寫的另外的算法詳解
最小生成樹-Prim算法(Java實現(xiàn))
最小生成樹-Kruskal算法(Java實現(xiàn))

謝謝~

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

最短路徑-Dijkstra算法(Java實現(xiàn))

最短路徑-Dijkstra算法(Java實現(xiàn))

算法應(yīng)用

核心思想

算法思路

注意

算法實現(xiàn)

完整代碼

圖的實現(xiàn)

具體過程

測試

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

最短路徑-Dijkstra算法(Java實現(xiàn))

算法應(yīng)用

核心思想

算法思路

注意

算法實現(xiàn)

完整代碼

圖的實現(xiàn)

具體過程

測試

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av