去,迪杰斯特拉:打印出路径,而不仅仅计算最短距离。

huangapple go评论158阅读模式
英文:

Go, Dijkstra : print out the path, not just calculate the shortest distance

问题

Go, Dijkstra:不仅计算最短距离,还要打印出路径。

我能够使用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]
英文:

Go, Dijkstra : print out the path, not just calculate the shortest distance.

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

I was able to find the shortest distance using Dijkstra algorithm, maybe not.
The code can be found here.

But it would be useless if I can't print out the path.
With a lot of pointers going on, I can't figure out how to print out the final path that takes the least amount of weights.

In short, how do I not only find the shortest distance, but also print out the shortest path on this given code?

The link is here:

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

And the snippet of the code is below:

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)
  }
}

I did something with array to see what is being updated.

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

This gives ms

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

答案1

得分: 7

当你在这里调整新的路径距离时:

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

设置一些数组元素(比如说,P代表“父节点”),指示你从Source到达了Destination

P[edge.Destination] = edge.Source

算法结束后,在这个数组中,每个顶点都会有其在从起始顶点出发的路径上的前驱节点。

PS. 好吧,不用数组和索引...

Vertex结构体中添加一个新字段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)
    }
}
英文:

When you adjust the new path distance here

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

Set some array element (say, P for "parent") to point that you have come to Destination from Source.

P[edge.Destination] = edge.Source

After the algorithm ends, in this array each vertex will have its predecessor on the path leading from the starting vertex.

PS. OK, not with arrays and indices ...

Add a new field Prev to the Vertex:

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

When adjusting distance:

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

And when you display the results:

for vertex1, distance1 := range distmap1 {
	fmt.Println(vertex1.Id, "=", distance1)
	if vertex1.Prev != nil {
	    fmt.Println (vertex1.Id, " -> ", vertex1.Prev.Id)
	}
}

答案2

得分: 0

最短路径打印使用Dijkstra算法的图(这里实现的是无向图)。以下代码打印了从源节点到图中所有其他节点的最短距离。

它还打印了从源节点到用户请求的节点的最短路径。
假设你需要在图中找到从AB的最短路径。然后将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];                                 // 用于打印路径

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));   //取消注释以创建有向图
    }
    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<<"节点"<<"         "<<"距离"<<endl;
    for(auto i=1;i<=nodes;++i){
        cout<<i<<"         "<<dist[i]<<endl;
    }
    /*----打印从源节点到请求节点的最短路径-------*/
    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<<"从"<<source_node<<"到"<<dest_node<<"的最短路径为:"<<endl;
    while(!path.empty()){
        if(path.size()==1) cout<<path.top();
        else cout<<path.top()<<"->";
        path.pop();
    }
    return 0;
}
/*测试用例*/
9 14        //---节点数,边数---
1 2 4       //---起点,终点,权重---对于边的数量
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           //---源节点
5           //-----需要路径的节点
---END---*/

希望对你有所帮助。

英文:

Shortest Path-Printing using Dijkstra's Algorithm for Graph (Here it is implemented for undirected Graph. The following code prints the shortest distance from the source_node to all the other nodes in the graph.

>>It also prints the shortest path from the source node to the node requested by the user.
Suppose,you need to find the shortest path from A to B in the graph. Then input A as the source node and B as the destination node.

Code

#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---*/

hope it helps

huangapple
  • 本文由 发表于 2013年11月11日 15:22:04
  • 转载请务必保留本文链接:https://go.coder-hub.com/19900903.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定