Doğrusal süre Grafik algoritması

Question

Doğrulanmamış bir grafik verildiğinde G = (V, E), iki rastgele köşe arasındaki toplam en kısa yol sayısını hesaplayan bir algoritma var mı? & v? Bence Dijkstra'nın algoritmasını kullanabiliriz.

Answer 1

Evet dijkstra kullanabilirsiniz. Herhangi bir düğüme toplam en kısa yol sayısını depolayan bir dizi oluşturun. Toplamı söyle. Tüm dizi üyesinin başlangıç ​​değeri, s kaynağı olduğu toplam [s] = 1 dışında 0'dır.

Dijkstra döngüde, bir düğümün en küçük yolunu karşılaştırırken, karşılaştırmanın sonucu küçükse, bu düğümün toplam dizisini toplam geçerli düğüm sayısıyla güncelleştirin. eşitse, o düğümün toplam dizisini toplam geçerli düğüm sayısıyla ekleyin. Bazı değişikliklerle wikipedia alınan

yalancı kod: kendisi tarafından

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[]