英文:
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算法的图(这里实现的是无向图)。以下代码打印了从源节点到图中所有其他节点的最短距离。
它还打印了从源节点到用户请求的节点的最短路径。
假设你需要在图中找到从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]; // 用于打印路径
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论