Самая короткая стоимость пути от всех узлов к определенному узлу в графе

Question

Я делаю проблему, в которой мне приходится вычислять общую стоимость перехода от одного конкретного узла (стартового узла) ко всем остальным узлам в направил, а затем вернулся с этих узлов на исходный узел. Теперь для первой части проблемы, идущей от начала к остальным узлам, я применил алгоритм dijkstra, но для второй части я подумал о том, что каждый узел должен зацикливаться как источник и использовать dijkstra для каждого узла. Но, если я не ошибаюсь, dijkstra вычисляет стоимость пути от одного исходного узла до остальной части узлов, что в этом случае приведет к большому количеству накладных расходов. Все, что мне нужно для второй части проблемы, - это самый короткий путь от всех узлов к одному конкретному узлу.

Вот что я делал (игнорируйте getchar, то есть только для ускорения ввода).

#include<set> 
#include<stdio.h> 
#include<vector> 
#include<limits.h> 
#include<cstdio> 
using namespace std; 

#define mp make_pair 
#define ft first 
#define sd second 
#define gc getchar 

vector< pair<int,int> > g[101000]; 
int n,m,sum,i,j,k,t,x,y,z; 
vector<int> dist; 
vector <int> vis; 

void scanint(int &x) 
{ 
    register int c = gc(); 
    x=0; 
    for(;(c<48||c>57);c=gc()); 
    for(;c>47&&c<58;c=gc()) 
    { 
     x=(x<<1)+(x<<3)+c-48; 
    } 
} 
void dijkstra(int source) 
{ 
    dist.clear(); 
    int i,j,k; 
    for(i=0;i<n;i++) 
    { 
     dist.push_back(INT_MAX); 
     vis.push_back(0); 
    } 
    dist[source] = 0; 
    set< pair<int,int> > s; // pair is dist, node_number 
    set< pair<int,int> >::iterator it; 

    for(i=0;i<n;i++) 
     s.insert(mp(dist[i],i)); 

    while(!s.empty()) 
    { 
     it = s.begin(); 
     pair<int,int> temp = *it; 
     s.erase(temp); // remove minimum val node 
     int cur = temp.sd; 
     int val = temp.ft; 

     if(val == INT_MAX) 
      return; 
     for(i=0;i<g[cur].size();i++) 
     { 
      int nb = g[cur][i].ft; 
      if(!vis[nb] && dist[nb] > val + g[cur][i].sd) 
      { 
       s.erase(mp(dist[nb],nb)); // erase old val 
       dist[nb] = val + g[cur][i].sd; 
       s.insert(mp(dist[nb],nb)); 
      } 
     } 
    } 
    s.clear(); 

} 
int main() 
{ 
    // std::ios::sync_with_stdio(false); 
    scanint(t); 
    for(int r=0;r<t;r++) 
    { 
     dist.clear(); 
     vis.clear(); 


     scanint(n); 
     scanint(m); 
     for(i=0;i<m;i++) 
      g[i].clear(); 

     for(i=0;i<m;i++) 
     { 
      scanint(x); 
      scanint(y); 
      scanint(z); 
      x--; y--; 
      g[x].push_back(mp(y,z)); 

     } 
     dijkstra(0); 
     sum=0; 
     for(int i=0;i<n;i++) 
     sum=sum+dist[i]; 
     for(int i=0;i<n;i++) 
     { 
      dijkstra(i); 
      sum=sum+dist[0]; 
     } 
     printf("%d\n",sum); 
     g[x].clear(); 
     for(int i=0;i<n;i++) 
     { 
      dist[i]=INT_MAX; 
     } 
    } 
    return 0; 
} 

Answer 1

Вы должны использовать алгоритм поиска пути, который производит shortest-path tree. Для этого можно использовать алгоритм Дейкстры и алгоритм Беллмана-Форда. Какой из них будет работать лучше, будет зависеть от density of your graph. Для разреженных графиков алгоритм Дейкстры будет быстрее.

Вы можете сделать следующее:

1. Вычислить дерево кратчайшего пути от исходного узла. Теперь у вас будут пути от вашего исходного узла до всех ваших пунктов назначения.
2. Обратное направление всех ребер на графике и снова вычислить дерево кратчайшего пути из исходного узла. Теперь это дерево будет содержать кратчайшие пути от ваших целевых узлов до исходного исходного узла.