我用neo4j创建了一个图形数据库,我对这个数据库的主要兴趣是找到MMORPG世界中城镇之间最便宜的传送路径。我使用Dijkstra算法得到如下最便宜的路径:
MATCH (s {name: 'Talking Island Village'}), (t {name: 'Town of Oren'}) CALLapoc.algo.dijkstra(s, t, 'HAS_A_PORT_TO>', 'cost') YIELD path, weight R
我需要用这样的方式划分一个图,即节点X和节点Y不再连通。另外,移除的边的权重之和必须是最低的。----- W ----- Y 3 2我首先认为我可以用一个循环来计算X和Y之间的最短路径,并去掉最便宜的边维基百科的搜索给我带来了Kernighan-Lin和Fiduccia-Mattheyses算法,但它们似乎是为了解决其他分区问题。
有标准的算法来解决这个问题吗?