标签: graph-algorithm

有谁知道如何编写一个编程图算法(C++代码会很棒),它找到一组给定节点和循环图中边的Kth最短路径？

例如,最短路径(可由Dijkstra或Bellman Ford找到)被认为是第1条最短路径.现在第二条最短路径是第一条最短路径之后的最短路径.现在我希望算法找到第K个最短路径.您将获得节点数,边数和边集数,如下所示:

节点数:5
个边数:6个
边:
0 1
0 2
1 2
2 3
3 1
1 4
源节点:0个
目标节点:4个

"请注意,此图表包含一个循环"谢谢.

假设我们找到了一棵最小的生成树.现在,我们只需要在MST中从A到Z的路径.我们怎样才能在O(n ^ 2)时间内做到这一点？

我们从根A开始.然后我们查看Ax(其中x是任何顶点)形式的树中的所有边.

然后,我们发现:AB,AC,AD等......然后对于每一个,我们寻找形式的边缘:Bx,Cx,Dx ......这显然不是O(n ^ 2).

那么在给定MST的情况下找到路径A - > Z的更好/更有效的方法是什么？

谢谢

我有一个程序允许用户在大小为1000乘750的JFrame上绘制顶点和边.现在我需要使用四叉树来根据单个象限中有多少个顶点来划分输入图.如果有人能指出我如何实现这个目标,我真的很感激吗？

附加信息:我有一个Edge类,它存储:source(顶点),target(顶点)和weight.我有一个Vertex类,它存储:name,x坐标,y坐标和Edge [] adjacentList.我还有一个Graph类,它存储两个ArrayLists:边和顶点.

BSP和MPI有什么区别？

我知道Pregel的图形计算框架是基于BSP的.他们为什么不直接使用MPI或开发基于MPI的框架？

将(x,y)坐标中的点相对于(0,0)移动/"旋转"x度的算法是什么？例如,在下图中,我想将点A移动到B,x度; A和(0,0)之间的距离在B和(0,0)之间应该相同.

我需要在前端环境中进行,即JavaScript.

对不起我的语言,因为英语是我的第二语言.

我试图将直线转换为称为Koch曲线的分形.给出了直线的2个点,然后我需要创建Koch曲线,其中我将线分成3段,然后使第二段成为等边三角形.见http://www.tgmdev.be/curvevonkoch.php.

到目前为止,我们将直线转换为4个相等的段,我需要弄清楚Koch曲线的所有坐标.

当2点的y坐标相同时,我想到了一条直线,它给了我水平线.如果是这样,我可以通过将第二个半段除以右三角形的cos(60)来找出等边三角形的3个点.如下:http: //www.themathpage.com/atrig/30-60-90-triangle.htm

我的问题是当直线是对角线时如何找到所有坐标,例如a(200,100),b(400,600)或a(400,500),b(100,500).

我需要在O(V + E)时间内确定无向图中的所有关键边.根据我的发现,我需要使用修改后的DF搜索,但我找到的所有伪代码算法都有低[v]和d [v],我不明白.有人可以向我解释O(V + E)桥确定算法吗？

我试图将一个沿直线(2点)的运动转换为沿着六角形路径的运动,我尝试了不同的公式并且不起作用.

我想找出基于A和B的P,Q,R,M的坐标.我希望有人建议一个更好的公式,它给出了移动长六边形路径的坐标.

我正在尝试创建一个回溯函数,它将返回从根到最短路径顺序的列表 GOAL

我的path_holder:

path_holder = {
   'node1':['node2','node3','node5'],  
   'node2':['node1','node8','node10'],
   'node3':['node4','node6']},
   'node4':['node2','node1','node3'],
   'node5':['DEADEND'],
   'node6':['GOAL']
    ....
    }

在我的path_holder输入中,它是BFS的输出,因此第一个节点是根,最后一个节点是目标.因为path_holder输入是BFS的输出,所以它在GOAL找到时停止,因此所有作为搜索所需的先前节点的分支的节点GOAL也被添加到其中path_holder.

目前我陷入了无限循环发生的while循环.我的一般策略是从GOAL节点开始并使用此节点的密钥来查找此密钥在另一个密钥(节点)列表中的位置.一旦我找到该节点(其列表包含密钥),我将节点的密钥设置为新目标.(令人困惑的句子抱歉)

这个图可能包含循环,这可能是我也得到无限循环的原因.

我的回溯功能:

def backtrace(path_holder, root, goal):
    dct = {}
    for d in path_holder:
            dct.update(d)
    rootnode = root.keys()[0]
    goal = goal.keys()[0]
    #x = len(path_holder)
    path = []
    path.append(goal)
    #for i in reversed(xrange(x):
    #   path_holder[i].keys()
    while goal != rootnode: 
        # find key that contains goal in list
        for i in dct:
            #print i
            for …

假设我在边缘加权无向图中具有源节点S,目的节点D和中间节点P1,P2,P3 ......的集合A. 我想找到顶点丕∈A是最大限度地减少DIST(S,PI)+ DIST(d,PI) ？此外,从S到D的总路径应仅包含集合A中的一个节点.什么是有效的算法？我不想用蛮力的方法.