标签: graph-algorithm

我正在尝试找到驾驶通过 A、B、C 和 D 点的最佳方式

有一些额外的限制 - 必须先达到某些点。说 D 必须在 B 之前到达。换句话说，对某些点进行排序。

如果没有额外的限制，Google Maps apis 可以帮助解决这个问题。是否有其他服务可以帮助解决此问题？有没有办法用我错过的谷歌地图 api 来做到这一点？

我只是在学习图论,我正在尝试将代码写入算法问题.问题涉及n群人,他们每个人与其中一个成员至少有一个相互的友谊.问题是要找到两个人之间最短的友谊关系.最短的友谊链接包含最少的人数.例如; A和B是共同的朋友,B和C是共同的朋友,如果A和C也是共同的朋友,那么AC和ABC是A和C之间的友谊链接但AC被认为更短,因为它涉及较小的个体.

我想知道哪种图理论算法适用于这种情况,我将不胜感激任何关于图论(免费维基)的免费互联网文档的建议.

可以通过运行 kruskal 算法找到最大生成树（只需更改边函数并首先考虑最大权重边）。我有兴趣找到最大权重欧几里得生成树。是否存在比 kruskal 更好的算法（更好的最坏情况运行时间）来找到这样的生成树？

我有两个问题要准确.首先,我想知道是否有一种简单的方法来调整马尔可夫聚类算法,以便我可以提前指定我希望在最后有多少个聚类.如果没有,你会推荐哪种类似的算法？

其次,应如何处理马尔可夫世界的重叠集群？

我知道DAG的定义,它是一个没有任何循环的有向图.我的问题是:我可以将2个独立的DAG视为一个DAG吗？如果没有,一组DAG的技术名称是什么？

我们有G = (V, E)一个comm的有向图.每个边缘具有不失败概率r(u, v)(定义为边缘权重)的网络,其位于区间[0,1]中.概率是独立的,因此从一个顶点到另一个顶点,如果我们乘以所有概率,我们得到整个路径没有失败的概率.

我需要一个有效的算法来找到其他给定的顶点,从一个给定的顶点最可靠的路径(即从第一个顶点到第二路径,该路径是最可能失败).我知道这log(r · s) = log r + log s会有所帮助.

这是我到目前为止 - :

DIJKSTRA-VARIANT (G, s, t)
for v in V:
    val[v] ? ?
A ? ?
Q ? V to initialize Q with vertices in V.
val[s] ? 0
while Q is not ? and t is not in A
    do x ? EXTRACT-MIN (Q)
    A ? A ? {x}
    for each vertex y ? Adj[x]
        do if val[x] …

此页面中的创意问题34 .

单调最短路径.给定边加权有向图,找到从s到每个其他顶点的单调最短路径.如果路径上每个边缘的权重严格增加或严格减小,则路径是单调的.

部分解决方案:按升序放松边缘,找到最佳路径; 然后按降序放松边缘并找到最佳路径.

我的问题:

假设我们按降序放松边缘,并且我们可以在一个点上选择多于1个边缘.我们将在什么基础上选择下一个优势？理想情况下,我们应该选择较小的边缘,因为它会最小化到该顶点的距离.但是如果离开它的所有边都具有大于当前边的权重的权重,那么这样做可能导致没有来自该顶点的进一步路径.

那么,我们怎样才能解决这个问题呢？

我在一本书中发现，为了展示家谱（家谱）树，最好使用带有拓扑排序的 DAG（有向无环图），但该算法取决于输入数据的顺序。

例如，

让我们说

1->2 costs 100
2->4 costs 600

所以1->2->4成本700

如果从 4 到 3 有一个花费 -500 的边怎么办？以及从 3 到 4 花费 200 的不同边缘

4->3 costs -500
3->4 costs 200

所以1->2->4->3->4成本400

哪个小于 700

所以被1->2->4->3->4认为是比1->2->4???更短的路径

我知道不允许循环，这是没有重复边的路径示例。

顶点呢？如果他们重复，这是 Floyd Warhsall 允许的循环吗？

因为我知道有不同类型的算法，一种允许一种循环而不允许其他类型的循环。

谁可以给我解释一下这个？回答问题，被1->2->4->3->4认为是比1->2->4???更短的路径

谢谢大家。

编辑：

这是一张图片，显示您不必两次访问同一条边。

我有一个相互连接的节点数组

我有下面的节点网络。这里以0为起点，我想尽可能多地移动节点，而一个节点仅移动一次。同样，在从0到目标节点的行程中，我只希望有一个奇数编号的节点（例如1、3、5、7）。现在，我需要找出从起始位置0开始可以走的最长路线。

范例：

int[] array = { 0, 9, 0, 2, 6, 8, 0, 8, 3, 0 };

在上图中，以下是可能性：

0 -> 6 -> 4 (valid path, length = 3 nodes)
0 -> 9 -> 1 (Not valid path, length as we have 2 odd numbers here 1 & 9)
0 -> 2 -> 3 -> 8 (valid path, length = 4 nodes)
0 -> 2 -> 3 -> 8 -> 5 (Not valid path as we have 2 odd numbers …