圖的最短路徑和拓?fù)渑判?/h2>

當(dāng)前比較行：0，shortTablePath結(jié)果：[0, 1, 5, 1000, 1000, 1000, 1000, 1000, 1000]
當(dāng)前比較行：1，shortTablePath結(jié)果：[0, 1, 4, 8, 6, 1000, 1000, 1000, 1000]
當(dāng)前比較行：2，shortTablePath結(jié)果：[0, 1, 4, 8, 5, 11, 1000, 1000, 1000]
當(dāng)前比較行：4，shortTablePath結(jié)果：[0, 1, 4, 7, 5, 8, 11, 14, 1000]
當(dāng)前比較行：3，shortTablePath結(jié)果：[0, 1, 4, 7, 5, 8, 10, 14, 1000]
當(dāng)前比較行：5，shortTablePath結(jié)果：[0, 1, 4, 7, 5, 8, 10, 13, 1000]
當(dāng)前比較行：6，shortTablePath結(jié)果：[0, 1, 4, 7, 5, 8, 10, 12, 17]
當(dāng)前比較行：7，shortTablePath結(jié)果：[0, 1, 4, 7, 5, 8, 10, 12, 16]
當(dāng)前比較行：8，shortTablePath結(jié)果：[0, 1, 4, 7, 5, 8, 10, 12, 16]

拓?fù)渑判?/h2>

2、圖的最短路徑

public class DnjavaDijstra {
    private final static int MAXVEX = 9;
    private final static int MAXWEIGHT = 65535;
    private int shortTablePath[] = new int[MAXVEX];// 記錄的是v0到某頂點(diǎn)的最短路徑和

     /**
     * 獲取一個(gè)圖的最短路徑
     * 首先在第一行找出一個(gè)最小的值（下標(biāo)1），表示v0到v1(k=1)的最短路徑。
     * 其次在遍歷第k行數(shù)據(jù)，滿足沒(méi)有被標(biāo)記并且graph[k][j]+min<shortTablePath[j],表示v0到vj存在更小的路徑。
     * 重復(fù)以上步驟，循環(huán)頂點(diǎn)個(gè)數(shù)減1次。
     */
    public void shortestPathDijstra(Graph graph) {
        int min;//最小值且沒(méi)確定是最短路徑
        int k = 0;// 記錄下標(biāo)
        //與shortTablePath對(duì)應(yīng)，表示每個(gè)節(jié)點(diǎn)最短路徑有沒(méi)有被確定
        boolean isgetPath[] = new boolean[MAXVEX];
        //獲取v0這一行的權(quán)值數(shù)組
        for (int v = 0; v < graph.getVertexSize(); v++) {
            shortTablePath[v] = graph.getMatrix()[0][v];// 
        }
        shortTablePath[0] = 0;
        isgetPath[0] = true;
        System.out.println("當(dāng)前比較行：0，shortTablePath結(jié)果："+Arrays.toString(shortTablePath));
        //遍歷行，除過(guò)第0行（數(shù)組）遍歷剩余graph.getVertexSize()-1行,不是按照順序遍歷，跟k有關(guān)
        for (int l = 1; l < graph.getVertexSize(); l++) {
            
            min = MAXWEIGHT;
            //在shortTablePath數(shù)組中查找最小值，且沒(méi)有被標(biāo)記過(guò)   
            for (int w = 0; w < graph.getVertexSize(); w++) {
                if (!isgetPath[w] && shortTablePath[w] < min) {
                    k = w;
                    min = shortTablePath[w];
                }
            }
            isgetPath[k] = true;
            //當(dāng)前行的每一列j數(shù)據(jù)與min之和如果小于shortTablePath[j],說(shuō)明v0到vv
            for (int j = 0; j < graph.getVertexSize(); j++) {
                if(!isgetPath[j]&&(min+graph.getMatrix()[k][j]<shortTablePath[j])){
                    shortTablePath[j] = min + graph.getMatrix()[k][j];
                }
            }
            System.out.println("當(dāng)前比較行："+k+"，shortTablePath結(jié)果："
+Arrays.toString(shortTablePath));
        }
        for(int i = 0;i<shortTablePath.length;i++){
            System.out.println("V0到V"+i+"的最短路徑為:"+shortTablePath[i]+"\n");
        }
        
    }
    
    public static void main(String[] args){
        Graph graph = new Graph(MAXVEX);
        graph.createGraph();
        DnjavaDijstra dijstra = new DnjavaDijstra();
        dijstra.shortestPathDijstra(graph);
    }
}

3、圖的拓?fù)渑判?/h3>

package com.dn.dijstra;

import java.util.Stack;

public class DnGraphTopologic {
    private int numVertexes;
    private VertexNode []  adjList;//鄰接頂點(diǎn)的一維數(shù)組
    public DnGraphTopologic(int numVertexes){
        this.numVertexes = numVertexes;
    }
    private void createGraph(){
        VertexNode node0 = new VertexNode(0,"v0");
        VertexNode node1 = new VertexNode(0,"v1");
        VertexNode node2 = new VertexNode(2,"v2");
        VertexNode node3 = new VertexNode(0,"v3");
        VertexNode node4 = new VertexNode(2,"v4");
        VertexNode node5 = new VertexNode(3,"v5");
        VertexNode node6 = new VertexNode(1,"v6");
        VertexNode node7 = new VertexNode(2,"v7");
        VertexNode node8 = new VertexNode(2,"v8");
        VertexNode node9 = new VertexNode(1,"v9");
        VertexNode node10 = new VertexNode(1,"v10");
        VertexNode node11 = new VertexNode(2,"v11");
        VertexNode node12 = new VertexNode(1,"v12");
        VertexNode node13 = new VertexNode(2,"v13");
        adjList = new VertexNode[numVertexes];
        adjList[0] =node0;
        adjList[1] =node1;
        adjList[2] =node2;
        adjList[3] =node3;
        adjList[4] =node4;
        adjList[5] =node5;
        adjList[6] =node6;
        adjList[7] =node7;
        adjList[8] =node8;
        adjList[9] =node9;
        adjList[10] =node10;
        adjList[11] =node11;
        adjList[12] =node12;
        adjList[13] =node13;
        node0.firstEdge = new EdgeNode(11);node0.firstEdge.next = new EdgeNode(5);node0.firstEdge.next.next = new EdgeNode(4);
        node1.firstEdge = new EdgeNode(8);node1.firstEdge.next = new EdgeNode(4);node1.firstEdge.next.next = new EdgeNode(2);
        node2.firstEdge = new EdgeNode(9);node2.firstEdge.next = new EdgeNode(6);node2.firstEdge.next.next = new EdgeNode(5);
        node3.firstEdge = new EdgeNode(13);node3.firstEdge.next = new EdgeNode(2);
        node4.firstEdge = new EdgeNode(7);
        node5.firstEdge = new EdgeNode(12);node5.firstEdge.next = new EdgeNode(8);
        node6.firstEdge = new EdgeNode(5);
        node8.firstEdge = new EdgeNode(7);
        node9.firstEdge = new EdgeNode(11);node9.firstEdge.next = new EdgeNode(10);
        node10.firstEdge = new EdgeNode(13);
        node12.firstEdge = new EdgeNode(9);
    }
    /**
     * 拓?fù)渑判?     * @author Administrator
     * @throws Exception 
     *
     */
    private void topologicalSort() throws Exception{
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        int k = 0;
        for(int i = 0;i<numVertexes;i++ ){
            if(adjList[i].in == 0){
                stack.push(i);
            }
        }
        while(!stack.isEmpty()){
            int pop = stack.pop();
            System.out.println("頂點(diǎn)："+adjList[pop].data);
            count++;
            for(EdgeNode node = adjList[pop].firstEdge;node!=null;node = node.next){
                k = node.adjVert;//下標(biāo)
                if(--adjList[k].in == 0){
                    stack.push(k);//入度為0,入棧
                }
            }
        }
        if(count<numVertexes){
            throw new Exception("完?duì)僮恿耍負(fù)渑判蚴?);
        }
    }
    
    //邊表頂點(diǎn)
    class EdgeNode{
        private int adjVert;
        private EdgeNode next;
        private int weight;
        public EdgeNode(int adjVert){
            this.adjVert = adjVert;
        }
        public int getAdjVert() {
            return adjVert;
        }
        public void setAdjVert(int adjVert) {
            this.adjVert = adjVert;
        }
        public EdgeNode getNext() {
            return next;
        }
        public void setNext(EdgeNode next) {
            this.next = next;
        }
        public int getWeight() {
            return weight;
        }
        public void setWeight(int weight) {
            this.weight = weight;
        }
        
    }
    
    //鄰接頂點(diǎn)
    class VertexNode{
        private int in;//入度
        private String data;
        private EdgeNode firstEdge;
        
        public VertexNode(int in,String data){
            this.in = in;
            this.data = data;
        }

        public int getIn() {
            return in;
        }

        public void setIn(int in) {
            this.in = in;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

        public EdgeNode getFirstEdge() {
            return firstEdge;
        }

        public void setFirstEdge(EdgeNode firstEdge) {
            this.firstEdge = firstEdge;
        }
        
    }
    
    public static void main(String [] args){
        DnGraphTopologic dnGraphTopologic = new DnGraphTopologic(14);
        dnGraphTopologic.createGraph();
        try {
            dnGraphTopologic.topologicalSort();
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

最后編輯于 ：2017.12.05 05:35:12

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。