标签: shortest-path

我正在尝试构建一个方法,在未加权的图形中返回从一个节点到另一个节点的最短路径.我考虑过使用Dijkstra,但这似乎有点矫枉过正,因为我只需要一对.相反,我已经实现了广度优先搜索,但问题是我的返回列表包含一些我不想要的节点 - 如何修改我的代码以实现我的目标？

public List<Node> getDirections(Node start, Node finish){
    List<Node> directions = new LinkedList<Node>();
    Queue<Node> q = new LinkedList<Node>();
    Node current = start;
    q.add(current);
    while(!q.isEmpty()){
        current = q.remove();
        directions.add(current);
        if (current.equals(finish)){
            break;
        }else{
            for(Node node : current.getOutNodes()){
                if(!q.contains(node)){
                    q.add(node);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("can't reach destination");
    }
    return directions;
}

假设有一个网格包含两个墙(被阻挡的单元格)以及放置在网格上任何位置的食物.

现在假设我们正在尝试确定将蚁群放置在该网格上的最佳位置,使得蚂蚁必须行进最小距离(在任何方向上往/来自群体的起始点)以获得最大量的食物.

到目前为止,我提出的最佳方法如下:

for each square on the grid
    use a shortest path algorithm to find the distance to/from each food source from this square
    sum these distances to find a number and put the number in that square
select the square with the smallest number

这种方法是否有效？有更有效的解决方案吗？

我需要通过无向图找到最短路径,其节点是实数(正和负)加权.这些权重就像您可以通过输入节点获得或松散的资源.

路径的总成本(资源总和)不是很重要,但必须大于0,并且长度必须尽可能短.

例如,考虑如下图:

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

最短的路径是AEFED

Dijkstra的算法本身并不起作用,因为它无法处理负值.所以,我想了几个解决方案:

首先使用Dijkstra算法计算从每个节点到出口节点的最短路径的长度,而不考虑权重.这可以像A*中的某种启发式值一样使用.我不确定这个解决方案是否可行,而且成本也很高.我也想过实现Floyd-Warshall的算法,但我不确定如何.

另一种解决方案是计算与Dijkstra算法不考虑权重的最短路径,如果计算路径的资源总和后,是小于零,经过的每个节点找到可能会很快增加资源和邻近节点,并将其添加到路径(如果需要,可以多次).如果有一个节点足以增加资源总和,但距计算的最短路径更远,则此解决方案将不起作用.

例如:

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

你能帮我解决这个问题吗？

编辑:如果在计算最短路径时,您到达资源总和等于零的点,该路径无效,因为如果没有更多的汽油则无法继续.

几天前,有人问我,如果我们在我们的环境中有一些代理商,并且他们想要从他们的消息来源到他们的目的地,那么我们如何才能找到他们所有人的最短路径,以便他们不应该在他们的步行.

问题的关键是所有代理人同时在环境中行走(可以通过无向加权图来建模),我们不应该有任何碰撞.我想到了这一点,但我找不到所有这些的最佳路径.但是肯定有太多启发式的想法来解决这个问题.

假定输入是图G(V,E),它们是在米剂:S ₁,S ₂,...,S _米在启动和图的节点它们应该去节点d ₁,... d _米处结束.也可能是节点S _i或D _i中存在冲突,但这些冲突并不重要,当它们位于其路径的内部节点时,它们不应该发生冲突.

如果它们的路径不应该有相同的内部节点,那将k-disjoint paths是NPC的一种问题,但是在这种情况下路径可以具有相同的节点,但是代理不应该同时在同一节点中.我不知道我能说出确切的问题陈述.如果令人困惑,请在评论中告诉我编辑它.

是否有任何最优和快速的算法(通过最优I均值,所有路径的长度总和尽可能最小,并且快速意味着良好的多项式时间算法).

我试图准确理解这些算法是如何工作的,但我一直无法找到一个简单的解释.如果有人能提供或指出我对这些算法的描述比原始论文中的描述更容易理解,我将不胜感激.谢谢.

我已经实现了Floyd Warshall算法并且它可以工作,但问题是我不知道如何找到所有未定义的路径.我在网上搜索过,但我只能找到如何检测图表是否有负循环的答案.

vector< vector <int> > floyd_warshall(vector< vector<int> > d, int n){
    for(int i = 0; i < n; i++) d[i][i] = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(d[j][i] + d[i][k] < d[j][k] and d[j][i] != INF and d[i][k] != INF){
                    d[j][k] = d[j][i] + d[i][k];
                }
            }
        }
    }

    return d;
}

在图表上运行算法后:

from: to:   weight:
0     1      1
1 …

这就是问题:

我有n个点(p1,p2,p3,... pn),每个点都可以以确定的成本x连接到任何其他点.

每个点属于一组点类型中的一个(例如"A""B""C""D"......).

方法的输入是我想要遵循的路径,例如"ABCADB".

输出是连接输入类型I的点的最短路径,例如"p1-p4-p32-p83-p43-p12",其中p1是A型,p4是B型,p32是C-类型,p83是A型,p43是D型,p12是B型.

"简单"的解决方案包括计算所有可能的路径,但计算成本非常高!

有人能找到更好的算法吗？

正如我在标题中所说,我不知道它是否存在!

更新:

阻止我使用Dijkstra和其他类似算法的关键点是我必须根据类型链接点.

作为输入,我有一个类型的数组,我必须按顺序链接.

这是Kent Fredric的图像(非常感谢),它描述了最初的情况(红色允许的链接)!

alt text http://img13.imageshack.us/img13/3856/immagineaol.jpg

一个真实的例子:

一个男人想早上去教堂,去餐馆,下午去博物馆.

地图上有6个教堂,30家餐厅和4个博物馆.

他希望教堂休息博物馆的距离是最小的.

这是一个我可以很容易地以非功能性方式解决的问题.

但是在Haskell中解决这个问题给了我很大的麻烦.在功能编程方面,我缺乏经验肯定是一个原因.

问题:

我有一个2D字段分为相同大小的矩形.一个简单的网格.一些矩形是空的空间(并且可以通过),而其他矩形是无法通过的.给定起始矩形A和目标矩形B,我如何计算两者之间的最短路径？只能垂直和水平移动,步骤单个矩形大.

我将如何在Haskell中完成此任务？代码片段肯定是受欢迎的,但肯定不是必要的.并且非常欢迎链接到更多资源!

谢谢!

我正在考虑对最短哈密顿路径(SHP)问题的扩展,我找不到解决它的方法.我知道它是NP完全的,但我想我会在这里提出想法,因为我不想简单地强行解决问题.

扩展非常简单:给定具有n个顶点的无向完整加权图,找到具有端点v和u的最短哈密顿路径.

因此,bruteforce仍然需要O(n!)时间,因为剩余的n -2个顶点可以在(n -2)中访问!方法.我试图找到一种方法,也许解决这个稍快.到目前为止,我努力寻找以有益的方式解决这个问题的方法.

有人会想知道如何利用终点顶点的知识吗？优选地与一些伪代码一起解释.找到的解决方案是最佳的.

我想它可以通过整数编程来解决,因为终端节点的知识是相当有限的,并且很容易避免循环,但它不会真正利用问题的组成.

我正在使用 networkx 来解决最短路径问题。我主要使用shortest_path。我想知道，使用当前版本的 networkx，是否可以限制最短路径计算？

下面的示例生成了 A 和 G 之间的这两条最短路径：

左边的图片显示了最小化“长度”属性时的最佳路线，右边的图片显示了最小化“高度”属性时的最佳路线。

如果我们计算这些路线的统计数据，我们会得到：

Best route by length: ['A', 'B', 'E', 'F', 'D', 'G']
Best route by height: ['A', 'C', 'E', 'G']
Stats best routes: {
                   'by_length': {'length': 13.7, 'height': 373.0}, 
                   'by_height': {'length': 24.8, 'height': 115.0}
                   }

有没有办法在计算最短路径时添加约束？（例如，通过最小化长度属性来计算最短路径，但同时保持height<300

计算图网络的代码：

Best route by length: ['A', 'B', 'E', 'F', 'D', 'G']
Best route by height: ['A', 'C', 'E', 'G']
Stats best routes: {
                   'by_length': {'length': 13.7, 'height': 373.0}, 
                   'by_height': {'length': 24.8, 'height': …