所以这是我当前的代码,我将在下面发布标题声明...

// 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。

示例图
c&#43;&#43; - 将Dijkstra算法与unordered_map图一起使用-LMLPHP

左边以下两个顶点的接近度将在右边:
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)

您可以通过遵循前辈来获得路径长度。

09-20 01:48