在OpenMP中实现Dijkstra最短路径算法时可能存在的范围问题？

Question

我一直在研究一个小程序，该程序使用OpenMP来计算给定图形中每个顶点的最短路径，以拆分多个线程之间的计算，而不是一次只执行一个顶点。虽然我目前的实现工作，但我想让它能够从格式为“vertex1 vertex2 weight”的文件中读取图形数据，因此图形不会被硬编码到程序中。

来源是这里：http://pastebin.com/bkR7QysB

编译如下：

g++ -fopenmp GraphTest.cpp WeightedGraph.cpp -o dijkstra 

使用下面的数据作为输入：

foo derp 50 
narf balls 30 
foo balls 20 
balls derp 60 
derp narf 40 
derp cox 30 
foo narf 50 
narf pie 99 
cox pie 15 
cox narf 10 

我的输出是：

Enter filename: lol.out 
Printing all edges currently in graph: 
(foo, derp) : cost 50 
(narf, balls) : cost 30 
(foo, balls) : cost 20 
(balls, derp) : cost 60 
(derp, narf) : cost 40 
(derp, cox) : cost 30 
(foo, narf) : cost 50 
(narf, pie) : cost 99 
(cox, pie) : cost 15 
(cox, narf) : cost 10 

[thread:0] Showing single-source shortest path run for source vertex balls. Format is (start, end) : cost. 
(balls, balls : cost 0) 
(balls, derp : cost 60) 

[thread:0] Showing single-source shortest path run for source vertex cox. Format is (start, end) : cost. 
(cox, cox : cost 0) 
(cox, narf : cost 10) 

[thread:1] Showing single-source shortest path run for source vertex derp. Format is (start, end) : cost. 
(derp, derp : cost 0) 
(derp, cox : cost 30) 

[thread:1] Showing single-source shortest path run for source vertex foo. Format is (start, end) : cost. 
(foo, foo : cost 0) 
(foo, narf : cost 50) 

[thread:2] Showing single-source shortest path run for source vertex narf. Format is (start, end) : cost. 
(narf, narf : cost 0) 
(narf, cox : cost 10) 

[thread:2] Showing single-source shortest path run for source vertex pie. Format is (start, end) : cost. 
(pie, pie : cost 0) 
(pie, cox : cost 15) 

这显然是不正确的 - 它应该打印从顶点到图形中每个其他顶点的最短路径，但这里只打印最短路径（它始终为0）和直接到其中一个直接路径相邻的邻居。它根本没有遍历图。最奇怪的一部分，然而，就是取消注释附近GraphTest.cpp的结束和注释掉文件处理代码，这样的图形数据是硬编码到程序块巨大，一切工作正常：

Printing all edges currently in graph: 
(foo, derp) : cost 50 
(narf, balls) : cost 30 
(foo, balls) : cost 20 
(balls, derp) : cost 60 
(derp, narf) : cost 40 
(derp, cox) : cost 30 
(foo, narf) : cost 50 
(narf, pie) : cost 99 
(cox, pie) : cost 15 
(cox, narf) : cost 10 

[thread:0] Showing single-source shortest path run for source vertex balls. Format is (start, end) : cost. 
(balls, balls : cost 0) 
(balls, foo : cost 20) 
(balls, narf : cost 30) 
(balls, cox : cost 40) 
(balls, pie : cost 55) 
(balls, derp : cost 60) 

[thread:0] Showing single-source shortest path run for source vertex cox. Format is (start, end) : cost. 
(cox, cox : cost 0) 
(cox, narf : cost 10) 
(cox, pie : cost 15) 
(cox, derp : cost 30) 
(cox, balls : cost 40) 
(cox, foo : cost 60) 

[thread:1] Showing single-source shortest path run for source vertex derp. Format is (start, end) : cost. 
(derp, derp : cost 0) 
(derp, cox : cost 30) 
(derp, narf : cost 40) 
(derp, pie : cost 45) 
(derp, foo : cost 50) 
(derp, balls : cost 60) 

[thread:1] Showing single-source shortest path run for source vertex foo. Format is (start, end) : cost. 
(foo, foo : cost 0) 
(foo, balls : cost 20) 
(foo, derp : cost 50) 
(foo, narf : cost 50) 
(foo, cox : cost 60) 
(foo, pie : cost 75) 

[thread:2] Showing single-source shortest path run for source vertex narf. Format is (start, end) : cost. 
(narf, narf : cost 0) 
(narf, cox : cost 10) 
(narf, pie : cost 25) 
(narf, balls : cost 30) 
(narf, derp : cost 40) 
(narf, foo : cost 50) 

[thread:2] Showing single-source shortest path run for source vertex pie. Format is (start, end) : cost. 
(pie, pie : cost 0) 
(pie, cox : cost 15) 
(pie, narf : cost 25) 
(pie, derp : cost 45) 
(pie, balls : cost 55) 
(pie, foo : cost 75) 

我真的不知道这里发生了什么。我能想到的唯一事情就是某个地方过早超出范围，导致我的图形对象行为异常，但如果这是真的，那么这两个输出应该是错的......希望有人比我更聪明，可以运行这并帮助我找出哪里出了问题。

Answer 1

我会提一些问题，通过您的代码阅读，而我看到：

1. 请注意，您的边缘图由一对索引，所以你在这里实现什么必须是有向图。因为你用（vi，vj）索引，边（v0，v1）和（v1，v0）是截然不同的，并且会有不同的值（甚至可能不存在！）。你应该想想办法来管理你的边缘，以便查找它们不依赖于顺序。

2. 我不明白你为什么在很大程度上依赖标准模板库的代码中使用char *。弦乐是你的朋友！

现在，我认为问题是你重新插入顶点。在你的代码中，你不做任何检查来确保你添加的顶点在图中不存在。相反，您只需分配一个新的顶点并将其放入顶点映射中。如果已经有一个具有该名称的顶点，它将在地图上被覆盖，并且您将失去对该数据的唯一引用。因此，你有内存泄漏，因为被替换的顶点不会被删除。

因此，如果您输入的文件是：

土著人基金球50 富土著人基金10

您的代码将创建并在两条线上增加一个土著人基金顶点。这是迄今为止我看到的唯一区别，但它很重要，并且会带来相当昂贵的错误以及内存泄漏。

作为一个方面说明，我不一定看到具有边缘对象的价值。您可以轻松地在每个顶点_neighbors列表中存储边的所有信息。使该列表成为地图，将相邻顶点的名称作为关键字，并将成本设为该值：

_neighborMap [v0.name（）] = cost;

具有边缘类型似乎会增加大量不必要的参考和复杂性。只是一个想法...

当我进一步观察你的代码时，我发现你实际上从不删除任何Vertex或Edge对象。如果你不想使用动态内存分配，只需让你的Graph使用Vertex的实例而不是指针。这些都是非常小的物体，这样你就不会去简单地做这样的事情多少钱自己在通过副本额外的指令方面：

_internalVertexMap[ "v0" ] = Vertex("v0");