所以这是我当前的代码,我将在下面发布标题声明...
// Using Dijkstra's
int Graph::closeness(string v1, string v2){
int edgesTaken = 0;
unordered_map<string, bool> visited;
unordered_map<string, int> distances;
string source = v1; // Starting node
while(source != v2 && !visited[source]){
// The node has been visited
visited[source] = 1;
// Set all initial distances to infinity
for(auto i = vertices.begin(); i != vertices.end(); i++){
distances[i->first] = INT_MAX;
}
// Consider all neighbors and calculate distances from the current node
// & store them in the distances map
for(int i = 0; i < vertices[source].edges.size(); i++){
string neighbor = vertices[source].edges[i].name;
distances[neighbor] = vertices[source].edges[i].weight;
}
// Find the neighbor with the least distance
int minDistance = INT_MAX;
string nodeWithMin;
for(auto i = distances.begin(); i != distances.end(); i++){
int currDistance = i->second;
if(currDistance < minDistance){
minDistance = currDistance;
nodeWithMin = i->first;
}
}
// There are no neighbors and the node hasn't been found yet
// then terminate the function and return -1. The nodes aren't connected
if(minDistance == INT_MAX)
return -1;
// Set source to the neighbor that has the shortest distance
source = nodeWithMin;
// Increment edgesTaken
edgesTaken++;
// clear the distances map to prepare for the next iteration
distances.clear();
}
return edgesTaken;
}
声明(这是一个无向图):
class Graph{
private:
// This holds the connected name and the corresponding we
struct EdgeInfo{
std::string name;
int weight;
EdgeInfo() { }
EdgeInfo(std::string n, int w) : name(n), weight(
};
// This will hold the data members of the vertices, inclu
struct VertexInfo{
float value;
std::vector<EdgeInfo> edges;
VertexInfo() { }
VertexInfo(float v) : value(v) { }
};
// A map is used so that the name is used as the index
std::unordered_map<std::string, VertexInfo> vertices;
注意:请不要建议我更改标题声明,我正在为一个已经编写了8个其他函数的项目做贡献,现在返回并更改任何内容为时已晚,因为随后必须重写所有其他函数
我目前收到错误的输出。但是,该函数正确处理了0距离的情况(如果未连接两个顶点,则该函数应返回-1)。如果两个节点的顶点近似相同(“Boston”,“Boston”),则该函数应返回0。
示例图
左边以下两个顶点的接近度将在右边:
Correct:
Trenton -> Philadelphia: 2
Binghamton -> San Francisco: -1
Boston -> Boston: 0
Palo Alto -> Boston: -1
Output of my function:
Trenton -> Philadelphia: 3
Binghamton -> San Francisco: -1
Boston -> Boston: 0
Palo Alto -> Boston: 3
我试图复制dijkstra的确切描述,但是我得到的读数不正确,我已经尝试了好一阵子->有人能指出我正确的方向吗?
最佳答案
您的实现是错误的,只有偶然的机会您才能获得“正确”的结果。
让我们手动做一个例子。从特伦顿到费城。我使用城市的首字母作为标签。
First iteration
visited = [(T, 1), (N, 0), (W, 0), (P, 0), (B, 0)]
minDistance = 3;
nodeWithMin = N;
edgesTaken = 1
second iteration
visited = [(T, 1), (N, 1), (W, 0), (P, 0), (B, 0)]
minDistance = 2;
nodeWithMin = W;
edgesTaken = 2
third iteration
visited = [(T, 1), (N, 1), (W, 1), (P, 0), (B, 0)]
minDistance = 2;
nodeWithMin = N;
edgesTaken = 3;
fourth iteration
N is already 1 so we stop. Can you see the errors?
传统上,Dijkstras最短路径算法是通过优先级队列实现的
dijkstra(graph, source)
weights is a map indexed by nodes with all weights = infinity
predecessor is a map indexed by nodes with all predecessors set to itself
unvisited is a priority queue containing all nodes
weights[source] = 0
unvisited.increase(source)
while unvisited is not empty
current = unvisited.pop();
for each neighbour to current
if weights[current] + edge_weight(current, neighbour) < weights[neighbour]
weights[neighbour] = weights[current] + + edge_weight(current, neighbour)
unvisited.increase(neighbour)
predecessors[neighbour] = current
return (weights, predecessors)
您可以通过遵循前辈来获得路径长度。