巨型图中的最短路径-Java 学习之路

现在我研究的图表通常不适合任何类型的内存或存储设备 . 我的问题是我需要在这些图中找到两个特定顶点之间的最短路径 .

我知道C的boost图库，我很开心 . 使用boost的图形库（以及其他图形库）的常用概念就是这样

在内存中创建顶点列表
在内存中创建边缘连接列表
调用您想要的图算法

这种方法适用于适合RAM的图形：

typedef adjacency_list<
    vecS,
    vecS,
    undirectedS,
    no_property,
    property<edge_weight_t, uint32_t> 
> TGraph;

void FindShortestPath(const TGraph& g, const uint32_t from, const uint32_t to)
{
    vector<TGraph::edge_descriptor> path;
    TGraph::vertex_descriptor v = vertex(to, g); // We want to start at the destination and work our way back to the source


    vector<TGraph::vertex_descriptor> p(num_vertices(g));
    vector<uint32_t> d(num_vertices(g));

    dijkstra_shortest_paths(g, vertex(from, g),
                            predecessor_map(make_iterator_property_map(p.begin(), get(vertex_index, g)))
                            .distance_map(make_iterator_property_map(d.begin(), get(vertex_index, g))));

    for(auto u = p[v]; u != v; v = u, u = p[v])
    {
        path.push_back(edge(u, v, g).first);
    }

    //// Write shortest path
    cout << "Distance: " << d[to] << endl;
    for(auto i = path.rbegin() + 1; i != path.rend(); ++i)
    {
        cout << source(*i, g) << " ";
    }

    cout << endl;
}

但由于我的图表很大，以上方法并不符合我的要求 . 我目前学习的图表有16个！顶点和每个顶点具有相同的度数，即64.而且，我认为任何顶点对之间的最短距离最小值小于20 .

那么关于图形的好处是它的顶点和边缘在数学上是完美定义的 . 有了这些知识，就没有必要在内存中创建整个图形来运行某些最短路径算法 .

我的想法是应该有一种方法可以使用boost库，每当我需要提供特定顶点的边连接时，我可以通过使用这个数学定义立即提供或计算它，仅在最短路径计算时这是必要的，然后一旦工作完成，释放它 .

我被困在这里，它超出了我的升级库或最短路径算法实现知识 .

你认为使用boost图库可以实现上述动态方法吗？如果有，怎么样？请提供一些示例或文件 .
你认为如果我用动态方法实现最短路径算法，那么与在内存中创建整个图形而不是运行算法相比，是否有可能在可接受的时间内解决最短路径？
如果"1"不可能但"2"是，那么您建议采用什么？

谢谢 .

巨型图中的最短路径

相关问题