5

去吧，Dijkstra：打印出路径，而不仅仅是计算最短距离。

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

我能够使用 Dijkstra 算法找到最短距离，也许不是。代码可以在这里找到。

但是，如果我不能打印出路径，那将毫无用处。由于有很多指针，我无法弄清楚如何打印出权重最少的最终路径。

简而言之，我如何不仅找到最短距离，而且在给定的代码上打印出最短路径？

链接在这里：

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

这给了毫秒

   [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

设置一些数组元素（例如，P对于“父”）指向您来自的Destination点Source。

P[edge.Destination] = edge.Source

算法结束后，在这个数组中，每个顶点都将在从起始顶点开始的路径上拥有其前身。

PS。好的，不是数组和索引...

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

Shortest Path-Printing using Dijkstra's Algorithm for Graph（这里是为无向图实现的。以下代码打印从 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 回答