algorithm - 从固定节点以最小成本到达节点的方法数

Question

在具有 m (m>n) 个双向边的加权图中有 n 个节点 (1,2.. n)。

所有权重都是正数并且没有多条边。

有一个固定原点(节点 1)。我们总是从原点开始旅行。

现在我们必须找到以最低成本到达每个节点(从原点开始)的方式(路径)数量。

(所有计算的路径都应该具有从原点到达该节点的最小成本)。

输入——第一行包含 n,m。

接下来的 m 行包含 u,v,w。 => u 和 v 之间有一条边，权重为 w(w>0)。

输出——为除原点以外的每个节点打印 n-1 行一行，包含以最小成本到达每个节点(从原点开始)的方法数。

样本测试-

4 5

1 2 5

1 3 3

3 2 2

3 4 7

2 4 5

输出——

2

1

3

这是我的解决方案，请检查这是否适用于所有情况，我使用了 Dijkstra + DP。我不确定代码的正确性。

#define pp pair<int,int>
vector< pp > adj[N]; //List to store graph
int dis[N],dp[N];

int main()
{
  ios::sync_with_stdio(0);
  int i,j,k,m,n,t;
  cin>>n>>m;
  for(i=0;i<m;i++)
  {
   int u,v,w;
   cin>>u>>v>>w;

   adj[u].push_back({w,v});       
   adj[v].push_back({w,v});
  }
priority_queue< pp , vector<pp > , greater<pp> > pq;   //Min Priority Queue
for(int i=0;i<=n;i++) dis[i] = INT_MAX;
dis[1] = 0;
dp[1] = 1;
pq.push({0,1});

while(!pq.empty())
{
  pp tp = pq.top();
  int u = tp.second;
  int d = tp.first;
  pq.pop();
  if(dis[u]<d) continue;       // We have better ans, so continue.

  for(i=0;i<adj[u].size();i++)  // Traversing all the egdes from node u 
    {
      int v = adj[u][i].second;  //Adjacent vertex v .
      int w = adj[u][i].first;
      if(d + w <= dis[v] )
       {
        if(d+w==dis[v])
        dp[v] += dp[u];     //Add the possible ways to the v from u

        if(d + w < dis[v])
          {
           dis[v] = d + w;  
           dp[v] = dp[u];   // Better ans so set it directly.
           pq.push({dis[v],v});  //Better ans found so push it into queue.
          }
       }
    }
 }

 cout<<endl;

 for(int i = 1;i<=n;i++)
 {
   cout<<i<<" dis = "<<dis[i]<<" ways = "<<dp[i]<<endl;
 }
 }

Answer 1

我认为您通过计算最小距离和否使问题过于复杂。路径在一起。

• 我认为您首先只需正常运行 dijsktra 并计算最小值一次运行中从源节点到所有其他节点的距离
• 然后，将当前存在双向边的图修改为单向边，从节点u -> 节点v，其中 distance[v] >= distance[u] 来自源节点 S。这将导致具有源 S 的层次图。
• 在此之后，您可以从源节点运行 BFS 或 DFS，并且数数通过添加编号到达该节点的方法。到达每个父节点的方法。