我在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. 我不明白你为什么要在严重依赖标准模板库的代码中使用字符*。字符串是你的朋友！

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

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

narf球50英尺narf 10

您的代码将在这两行上创建并添加一个narf顶点。到目前为止，这是我看到的唯一不同之处，但它很重要，而且会带来代价相当高的bug以及内存泄漏。

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

_neighborMap v0.name() =成本；

拥有边缘类型似乎只是增加了许多不必要的引用和复杂性。只是一个想法..。

当我进一步查看您的代码时，我发现您实际上从未删除过任何Vertex或Edge对象。如果你不想使用动态内存分配，只需要让你的Graph使用Vertex的实例而不是指针。这些都是非常小的对象，所以你不需要花费太多的额外指令，只需简单地做如下操作：

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