線形時間グラフアルゴリズム

Question

無向グラフG =（V、E）の場合、任意の2つの頂点u & v間の最短経路の総数を計算するアルゴリズムがありますか？私はDijkstraのアルゴリズムを利用できると思う。

Answer 1

はい、dijkstraを使用できます。任意のノードへの最短パスの総数を格納する配列を作成します。それを合計と呼ぶ。 sがsourceであるtotal [s] = 1を除き、すべての配列メンバの初期値は0です。

dijkstraループでは、ノードの最小パスを比較する場合、比較結果が小さい場合は、そのノードの合計配列を現在のノードの合計数で更新します。等しい場合は、そのノードの合計配列に現在のノードの合計数を加えます。

いくつかの変更でウィキペディアから取られた擬似コード：自身で

function Dijkstra(Graph, source): 

    create vertex set Q 

    for each vertex v in Graph:    // Initialization 
     dist[v] ← INFINITY     // Unknown distance from source to v 
     total[v] ← 0      // total number of shortest path 
     add v to Q       // All nodes initially in Q (unvisited nodes) 

    dist[source] ← 0      // Distance from source to source 
    total[source] ← 1      // total number of shortest path of source is set to 1 

    while Q is not empty: 
     u ← vertex in Q with min dist[u] // Source node will be selected first 
     remove u from Q 

     for each neighbor v of u:   // where v is still in Q. 
      alt ← dist[u] + length(u, v) 
      if alt < dist[v]:    // A shorter path to v has been found 
       dist[v] ← alt 
       total[v] ← total[u]   // update the total array of that node with the number of total array of current node 
      elseif alt = dist[v] 
       total[v] ← total[v] + total[u] // add the total array of that node with the number of total array of current node 

    return dist[], total[]