国产精品久久久天天影视香蕉,欧洲午夜一区二区免费,亚洲绝美精品一区二区

漫畫：圖的 “最短路徑” 問題 | 技術頭條

發布時間：2019-04-12 02:14:07

技術頭條： 干貨、簡潔、多維全面。更多云計算精華知識盡在眼前，get要點、solve難題，統統不在話下！

作者：蠢萌的小灰

轉自：程序員小灰

—————? 第二天? —————

如何遍歷呢？

第一層，遍歷頂點A：

第二層，遍歷A的鄰接頂點B和C：

第三層，遍歷頂點B的鄰接頂點D、E，遍歷頂點C的鄰接頂點F：

第四層，遍歷頂點E的鄰接頂點G，也就是目標節點：

由此得出，圖中頂點A到G的（第一條）最短路徑是A-B-E-G：

換句話說，就是尋找從A到G之間，權值之和最小的路徑。

————————————

究竟什么是迪杰斯特拉算法？它是如何尋找圖中頂點的最短路徑呢？

這個算法的本質，是不斷刷新起點與其他各個頂點之間的?“距離表”。

讓我們來演示一下迪杰斯特拉的詳細過程：

第1步，創建距離表。表中的Key是頂點名稱，Value是 從起點A到對應頂點的已知最短距離 。但是，一開始我們并不知道A到其他頂點的最短距離是多少，Value默認是無限大：

第2步，遍歷起點A，找到起點A的鄰接頂點B和C。從A到B的距離是5，從A到C的距離是2。把這一信息刷新到距離表當中：

第3步，從距離表中找到從A出發距離最短的點，也就是頂點C。

第4步，遍歷頂點C，找到頂點C的鄰接頂點D和F（A已經遍歷過，不需要考慮）。從C到D的距離是6，所以A到D的距離是2+6=8；從C到F的距離是8，所以從A到F的距離是2+8=10。把這一信息刷新到表中：

接下來重復第3步、第4步所做的操作：

第5步，也就是第3步的重復，從距離表中找到從A出發距離最短的點（C已經遍歷過，不需要考慮），也就是頂點B。

第6步，也就是第4步的重復，遍歷頂點B，找到頂點B的鄰接頂點D和E（A已經遍歷過，不需要考慮）。從B到D的距離是1，所以A到D的距離是5+1=6， 小于距離表中的8 ；從B到E的距離是6，所以從A到E的距離是5+6=11。把這一信息刷新到表中：

（在第6步，A到D的距離從8刷新到6，可以看出距離表所發揮的作用。距離表通過迭代刷新，用新路徑長度取代舊路徑長度，最終可以得到從起點到其他頂點的最短距離）

第7步，從距離表中找到從A出發距離最短的點（B和C不用考慮），也就是頂點D。

第8步，遍歷頂點D，找到頂點D的鄰接頂點E和F。從D到E的距離是1，所以A到E的距離是6+1=7， 小于距離表中的11 ；從D到F的距離是2，所以從A到F的距離是6+2=8 ， 小于距離表中的10 。把這一信息刷新到表中：

第9步，從距離表中找到從A出發距離最短的點，也就是頂點E。

第10步，遍歷頂點E，找到頂點E的鄰接頂點G。從E到G的距離是7，所以A到G的距離是7+7=14。把這一信息刷新到表中：

第11步，從距離表中找到從A出發距離最短的點，也就是頂點F。

第10步，遍歷頂點F，找到頂點F的鄰接頂點G。從F到G的距離是3，所以A到G的距離是8+3=11， 小于距離表中的14 。把這一信息刷新到表中：

就這樣，除終點以外的全部頂點都已經遍歷完畢，距離表中存儲的是從起點A到所有頂點的最短距離。顯然，從A到G的最短距離是11。（路徑：A-B-D-F-G）

按照上面的思路，我們來看一下代碼實現：


/**
 * Dijkstra最短路徑算法
 */
publicstaticMap<Integer,Integer> dijkstra(Graph graph,int startIndex){
//創建距離表，存儲從起點到每一個頂點的臨時距離
Map<Integer,Integer> distanceMap =newHashMap<Integer,Integer>();
//記錄遍歷過的頂點
Set<Integer> accessedSet =newHashSet<Integer>();
//圖的頂點數量
int size = graph.vertexes.length;
//初始化最短路徑表，到達每個頂點的路徑代價默認為無窮大
for(int i=1; i<size; i++){
        distanceMap.put(i,Integer.MAX_VALUE);
}
//遍歷起點，刷新距離表
    accessedSet.add(0);
List<Edge> edgesFromStart = graph.adj[startIndex];
for(Edge edge : edgesFromStart)
{
        distanceMap.put(edge.index, edge.weight);
}
//主循環，重復 遍歷最短距離頂點和刷新距離表 的操作
for(int i=1; i<size; i++)
{
//尋找最短距離頂點
int minDistanceFromStart =Integer.MAX_VALUE;
int minDistanceIndex =-1;
for(int j=1; j<size; j++)
{
if(!accessedSet.contains(j)&& distanceMap.get(j)< minDistanceFromStart)
{
                minDistanceFromStart = distanceMap.get(j);
                minDistanceIndex = j;
}
}
if(minDistanceIndex ==-1){
break;
}
//遍歷頂點，刷新距離表
        accessedSet.add(minDistanceIndex);
for(Edge edge : graph.adj[minDistanceIndex])
{
if(accessedSet.contains(edge.index)){
continue;
}
int weight = edge.weight;
int preDistance = distanceMap.get(edge.index);
if(weight !=Integer.MAX_VALUE  &&(minDistanceFromStart+ weight < preDistance))
{
                distanceMap.put(edge.index, minDistanceFromStart + weight);
}
}
}
return distanceMap;
}
publicstaticvoid main(String[] args){
Graph graph =newGraph(7);
    initGraph(graph);
Map<Integer,Integer> distanceMap = dijkstra(graph,0);
int distance = distanceMap.get(6);
System.out.println(distance);
}
/**
 * 圖的頂點
 */
privatestaticclassVertex{
String data;
Vertex(String data){
this.data = data;
}
}
/**
 * 圖的邊
 */
privatestaticclassEdge{
int index;
int weight;
Edge(int index,int weight){
this.index = index;
this.weight = weight;
}
}
/**
 * 圖
 */
privatestaticclassGraph{
privateVertex[] vertexes;
privateLinkedList<Edge> adj[];
Graph(int size){
//初始化頂點和鄰接矩陣
        vertexes =newVertex[size];
        adj =newLinkedList[size];
for(int i=0; i<adj.length; i++){
            adj[i]=newLinkedList<Edge>();
}
}
}
privatestaticvoid initGraph(Graph graph){
    graph.vertexes[0]=newVertex("A");
    graph.vertexes[1]=newVertex("B");
    graph.vertexes[2]=newVertex("C");
    graph.vertexes[3]=newVertex("D");
    graph.vertexes[4]=newVertex("E");
    graph.vertexes[5]=newVertex("F");
    graph.vertexes[6]=newVertex("G");
    graph.adj[0].add(newEdge(1,5));
    graph.adj[0].add(newEdge(2,2));
    graph.adj[1].add(newEdge(0,5));
    graph.adj[1].add(newEdge(3,1));
    graph.adj[1].add(newEdge(4,6));
    graph.adj[2].add(newEdge(0,2));
    graph.adj[2].add(newEdge(3,6));
    graph.adj[2].add(newEdge(5,8));
    graph.adj[3].add(newEdge(1,1));
    graph.adj[3].add(newEdge(2,6));
    graph.adj[3].add(newEdge(4,1));
    graph.adj[3].add(newEdge(5,2));
    graph.adj[4].add(newEdge(1,6));
    graph.adj[4].add(newEdge(3,1));
    graph.adj[4].add(newEdge(6,7));
    graph.adj[5].add(newEdge(2,8));
    graph.adj[5].add(newEdge(3,2));
    graph.adj[5].add(newEdge(6,3));
    graph.adj[6].add(newEdge(4,7));
    graph.adj[6].add(newEdge(5,3));
}