字符串型图中的 Dijkstra 算法

Question

我正在制作一个城际路线规划程序，其中形成的图形具有字符串类型的节点（例如 LHR、ISB、DXB）。它是无向但有权重的，初始化为：

map<pair<string, string>, int> city;

然后我可以添加边，例如：

Graph g;
g.addEdge("DXB", "LHR", 305);
g.addEdge("HTR", "LHR", 267);
g.addEdge("HTR", "ISB", 543);

结果输出将是：

        ISB     LHR
DXB     0       305
HTR     543     267

现在，问题是...我正在尝试在此图中实现 Dijkstra 算法，但到目前为止无法在字符串类型节点上正确运行它并且反对在int 类型的节点。有人可以指导我以最有效的方式完成实施的正确步骤吗？

Answer 1

核心问题是，当我们处理具有整数顶点的图时，邻接表的索引代表节点（因为索引也是数字）。现在我们可以使用 map<string,vector<string, int> > adj 而不是像 vector<pair<int, int> > adj[N] 这样的邻接表。现在 adj["DXB"] 将包含一个形式为 <string, int> 的向量对，它是连接到 "DXB".

的城市的 <name, weight>

如果这种方法看起来很复杂，那么您可以使用一些额外的内存将一个城市映射到一个数字，然后考虑到该图具有整数顶点，您可以对所有内容进行编码。

Answer 2

图形应用程序使用的数据结构对编码的效率和易用性有很大影响。

许多设计都是从节点开始的。我想在被建模的问题中，节点通常具有物理现实，而 link 可以是抽象关系。所以开始写一个节点class比较自然，后面再补上link

然而，在编写解决图论问题的算法时，很明显 link 才是真正的重点。所以，让我们从 link class.

开始

class cLink
{
public:
    cLink(int c = 1)
        : myCost(c)
    {
    }
    int myCost;         // a constraint e.g. distance of a road, max xapacity of a pipe
    int myValue;        // a calculated value, e.g. actual flow through a pipe
};

如果我们将节点的外边存储在以目标节点索引为键的映射中，则该映射将是源节点的属性。

class cNode
{
public:
    cNode(const std::string &name = "???")
        : myName(name)
    {
    }
    std::string myName;
    std::map<int, cLink> myLink;    // out edges of node, keyed by destination
};

我们有link个节点，所以我们准备构建一个class来存储图

class cGraph {
public:
std::map<int, cNode> myG; // the graph, keyed by internal node index
};

节点索引从何而来？人类的计算能力很差，所以最好计算机在添加节点时生成索引。

cGraph::createNode( const std::string& name )
{
    int n = myG.size();
    myG.insert(std::make_pair(n, cNode(name)));
}

不要执行这个！它有一个障碍——它可以创建两个同名的节点。我们需要能够检查具有指定名称的节点是否存在。

int cGraph::find(const std::string &name)
{
    for (auto n : myG)
    {
        if (n.second.myName == name)
        {
            return n.first;
        }
    }
    return -1;
}

这是低效的。但是，只需要在添加节点时执行一次。然后搜索图的算法可以使用索引号快速查找节点。

现在我们可以防止创建两个具有相同名称的节点

    int cGraph::findoradd(const std::string &name)
    {
        // search among the existing nodes
        int n = find(name);
        if (n < 0)
        {
            // node does not exist, create a new one
            // with a new index and add it to the graph
            n = myG.size();
            myG.insert(std::make_pair(n, cNode(name)));
        }
        return n;
    }

人类除了是可怕的计数器之外，还对自己的计数能力过于自信。当他们指定这样的图表时

1 -> 2
1 -> 3

大家不要上当，我们把这些数字当成名字，继续使用我们自己的节点索引系统。

/** Add costed link between two nodes
 *
 * If the nodes do not exist, they will be added.
 *
 */

            void addLink(
                const std::string & srcname,
                const std::string & dstname,
                double cost = 1)
            {
                int u = findoradd(srcname);
                int v = findoradd(dstname);
                myG.find(u)->second.myLink.insert(
                           std::make_pair(v, cLink(cost)));
                if (!myfDirected)
                    myG.find(v)->second.myLink.insert(
                           std::make_pair(u, cLink(cost)));
            }

添加了一些 getter 和 setter 之后，我们就可以开始实现图形算法了！

要查看使用这些想法的完整实现，包括 Dijsktra，请查看 PathFinder。

字符串型图中的 Dijkstra 算法

Dijkstra's Algorithm in String-type Graph

c++

algorithm

stl

graph

dijkstra