dongsu7049
dongsu7049
2013-11-11 07:22

开始,Dijkstra:打印出路径,而不仅仅是计算最短距离

  • dijkstra
  • algorithm
  • graph
已采纳

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]
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • doulu4534 doulu4534 8年前

    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)
        }
    }
    
    点赞 评论 复制链接分享
  • doue8385 doue8385 2年前

    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

    点赞 评论 复制链接分享