5

Go, Dijkstra : 最短距離を計算するだけでなく、パスを出力します。

http://play.golang.org/p/A2jnzKcbWD

ダイクストラ アルゴリズムを使用して最短距離を見つけることができました。コードはここにあります。

しかし、パスを出力できなければ意味がありません。多くのポインターが進行中であるため、重みが最小になる最終的なパスを出力する方法がわかりません。

要するに、最短距離を見つけるだけでなく、この特定のコードで最短経路を出力するにはどうすればよいですか?

リンクはこちら：

http://play.golang.org/p/A2jnzKcbWD

コードのスニペットは次のとおりです。

const MAXWEIGHT = 1000000

type MinDistanceFromSource map[*Vertex]int

func (G *Graph) Dijks(StartSource, TargetSource *Vertex) MinDistanceFromSource {
  D := make(MinDistanceFromSource)
  for _, vertex := range G.VertexArray {
    D[vertex] = MAXWEIGHT
  }
  D[StartSource] = 0

  for edge := range StartSource.GetAdEdg() {
    D[edge.Destination] = edge.Weight
  }
  CalculateD(StartSource, TargetSource, D)
  return D
}

func CalculateD(StartSource, TargetSource *Vertex, D MinDistanceFromSource) {
  for edge := range StartSource.GetAdEdg() {
    if D[edge.Destination] > D[edge.Source]+edge.Weight {
      D[edge.Destination] = D[edge.Source] + edge.Weight
    } else if D[edge.Destination] < D[edge.Source]+edge.Weight {
      continue
    }
    CalculateD(edge.Destination, TargetSource, D)
  }
}

何が更新されているかを確認するために、配列で何かをしました。

http://play.golang.org/p/bRXYjnIGxy

これによりmsが得られます

   [A->D D->E E->F F->T B->E E->D E->F F->T]
4

2 に答える 2

7

ここで新しい経路距離を調整すると

   if D[edge.Destination] > D[edge.Source]+edge.Weight {
      D[edge.Destination] = D[edge.Source] + edge.Weight

fromに到達したことを指すように、いくつかの配列要素 (たとえば、P「親」) を設定します。DestinationSource

P[edge.Destination] = edge.Source

アルゴリズムが終了すると、この配列内の各頂点は、開始頂点から続くパス上にその前の頂点を持ちます。

PS。OK、配列とインデックスではありません...

Prev頂点に新しいフィールドを追加します。

type Vertex struct {
    Id      string
    Visited bool
    AdjEdge []*Edge
    Prev *Vertex
}

距離を調整する場合：

if D[edge.Destination] > D[edge.Source]+edge.Weight {
    D[edge.Destination] = D[edge.Source] + edge.Weight
    edge.Destination.Prev = edge.Source

結果を表示すると、次のようになります。

for vertex1, distance1 := range distmap1 {
    fmt.Println(vertex1.Id, "=", distance1)
    if vertex1.Prev != nil {
        fmt.Println (vertex1.Id, " -> ", vertex1.Prev.Id)
    }
}
于 2013-11-11T07:24:51.877 に答える
0

ダイクストラのアルゴリズムを使用したグラフの最短パス印刷 (ここでは、無向グラフに対して実装されています。次のコードは、source_node からグラフ内の他のすべてのノードまでの最短距離を印刷します。

また、ソース ノードからユーザーが要求したノードまでの最短パスも表示されます。グラフ内のAからB への最短経路を見つける必要があるとします。次に、 Aをソース ノードとして入力し、Bを宛先ノードとして入力します。

コード

#include<bits/stdc++.h>
using namespace std;
#define INF (unsigned)!((int)0)

const int MAX=2e4;
vector<pair<int,int>> graph[MAX];

bool visit[MAX];
int dist[MAX];

multiset<pair<int,int>> s;
int parent[MAX];                                 // used to print the path

int main(){
    memset(visit,false,sizeof(visit));
    memset(dist,INF,sizeof(dist));
    memset(parent,-1,sizeof(parent));

    int nodes,edges;        cin>>nodes>>edges;
    for(auto i=0;i<edges;++i){
        int a,b,w;
        cin>>a>>b>>w;
        graph[a].push_back(make_pair(b,w));
        graph[b].push_back(make_pair(a,w));   //Comment it to make the Directed Graph
    }
    int source_node;    cin>>source_node;
    dist[source_node]=0;
    s.insert(make_pair(0,source_node));

    while(!s.empty()){
        pair<int,int> elem=*s.begin();
        s.erase(s.begin());
        int node=elem.second;
        if(visit[node])continue;
        visit[node]=true;
        for(auto i=0;i<graph[node].size();++i){
            int dest=graph[node][i].first;
            int w=graph[node][i].second;
            if(dist[node]+w<dist[dest]){
                dist[dest]=dist[node]+w;
                parent[dest]=node;
                s.insert(make_pair(dist[dest],dest));
            }
        }
    }
    cout<<"NODE"<<"         "<<"DISTANCE"<<endl;
    for(auto i=1;i<=nodes;++i){
        cout<<i<<"         "<<dist[i]<<endl;
    }
    /*----PRINT SHORTEST PATH FROM THE SOURCE NODE TO THE NODE REQUESTED-------*/
    int node_for_path;      cin>>node_for_path;
    int dest_node=node_for_path;
    stack<int> path;
    while(parent[node_for_path]!=source_node){
        path.push(node_for_path);
        node_for_path=parent[node_for_path];
    }
    path.push(node_for_path);
    path.push(source_node);
    cout<<"Shortest Path from "<<source_node<<"to "<<dest_node<<":"<<endl;
    while(!path.empty()){
        if(path.size()==1) cout<<path.top();
        else cout<<path.top()<<"->";
        path.pop();
    }
    return 0;
}
/*TEST CASE*/
9 14        //---NODES,EDGES---
1 2 4       //---START,END,WEIGHT---FOR THE NO OF EDGES
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 1 8
2 8 11
8 9 7
9 7 6
9 3 2
6 3 4
4 6 14
1           //---SOURCE_NODE
5           //-----NODE TO WHICH PATH IS REQUIRED
---END---*/

それが役に立てば幸い

于 2019-01-03T06:44:03.820 に答える