日韩高清二区,在线日韩电影,亚洲va欧美va人人爽午夜

漫畫(huà)：圖的 “最短路徑” 問(wèn)題 | 技術(shù)頭條

發(fā)布時(shí)間：2019-04-12 02:14:07

技術(shù)頭條： 干貨、簡(jiǎn)潔、多維全面。更多云計(jì)算精華知識(shí)盡在眼前，get要點(diǎn)、solve難題，統(tǒng)統(tǒng)不在話下！

作者：蠢萌的小灰

轉(zhuǎn)自：程序員小灰

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

如何遍歷呢？

第一層，遍歷頂點(diǎn)A：

第二層，遍歷A的鄰接頂點(diǎn)B和C：

第三層，遍歷頂點(diǎn)B的鄰接頂點(diǎn)D、E，遍歷頂點(diǎn)C的鄰接頂點(diǎn)F：

第四層，遍歷頂點(diǎn)E的鄰接頂點(diǎn)G，也就是目標(biāo)節(jié)點(diǎn)：

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

換句話說(shuō)，就是尋找從A到G之間，權(quán)值之和最小的路徑。

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

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

這個(gè)算法的本質(zhì)，是不斷刷新起點(diǎn)與其他各個(gè)頂點(diǎn)之間的?“距離表”。

讓我們來(lái)演示一下迪杰斯特拉的詳細(xì)過(guò)程：

第1步，創(chuàng)建距離表。表中的Key是頂點(diǎn)名稱(chēng)，Value是 從起點(diǎn)A到對(duì)應(yīng)頂點(diǎn)的已知最短距離 。但是，一開(kāi)始我們并不知道A到其他頂點(diǎn)的最短距離是多少，Value默認(rèn)是無(wú)限大：

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

第3步，從距離表中找到從A出發(fā)距離最短的點(diǎn)，也就是頂點(diǎn)C。

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

接下來(lái)重復(fù)第3步、第4步所做的操作：

第5步，也就是第3步的重復(fù)，從距離表中找到從A出發(fā)距離最短的點(diǎn) （C已經(jīng)遍歷過(guò)，不需要考慮），也就是頂點(diǎn)B。

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

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

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

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

第9步，從距離表中找到從A出發(fā)距離最短的點(diǎn)，也就是頂點(diǎn)E。

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

第11步，從距離表中找到從A出發(fā)距離最短的點(diǎn)，也就是頂點(diǎn)F。

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

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

按照上面的思路，我們來(lái)看一下代碼實(shí)現(xiàn)：


/**
 * Dijkstra最短路徑算法
 */
publicstaticMap<Integer,Integer> dijkstra(Graph graph,int startIndex){
//創(chuàng)建距離表，存儲(chǔ)從起點(diǎn)到每一個(gè)頂點(diǎn)的臨時(shí)距離
Map<Integer,Integer> distanceMap =newHashMap<Integer,Integer>();
//記錄遍歷過(guò)的頂點(diǎn)
Set<Integer> accessedSet =newHashSet<Integer>();
//圖的頂點(diǎn)數(shù)量
int size = graph.vertexes.length;
//初始化最短路徑表，到達(dá)每個(gè)頂點(diǎn)的路徑代價(jià)默認(rèn)為無(wú)窮大
for(int i=1; i<size; i++){
        distanceMap.put(i,Integer.MAX_VALUE);
}
//遍歷起點(diǎn)，刷新距離表
    accessedSet.add(0);
List<Edge> edgesFromStart = graph.adj[startIndex];
for(Edge edge : edgesFromStart)
{
        distanceMap.put(edge.index, edge.weight);
}
//主循環(huán)，重復(fù) 遍歷最短距離頂點(diǎn)和刷新距離表 的操作
for(int i=1; i<size; i++)
{
//尋找最短距離頂點(diǎn)
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;
}
//遍歷頂點(diǎn)，刷新距離表
        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);
}
/**
 * 圖的頂點(diǎn)
 */
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){
//初始化頂點(diǎn)和鄰接矩陣
        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));
}