是否有任何通用或简单的算法可以将加权图转换为非加权图(其中每条边具有相同的权重(？
我知道一种叫做Djikstra算法的算法，当找到图中任意两个顶点之间的最短距离时，它的工作原理与加权图上的BFS非常相似。
但我想稍微改变一下任何加权图中的问题，其中每条边都在权重集{1,2,3,4，…，n}中，其中该集中的每个数字都是边的权重。这样，如果每条边都是相同的权重，我可以直接对其应用BFS或DFS。
我想找到一种修改图的方法，使修改图中的每条边都具有相同的权重(这意味着修改图中最好每条边的权重为1(。我知道我可能需要删除或添加边，添加中间顶点，或者从原始图中删除任何顶点来满足这一点。
关于如何做到这一点，有一个大致的想法吗？我从来没有在StackOverflow上看到过这样的帖子。
注意：加权图不会阻止您使用BFS/DFS。
话虽如此，你当然可以通过添加一堆中间音符将加权图转换为未加权图。然而，我不建议你这样做，因为已经有了像dijkstra、bellman-ford、floyd-warshall这样的算法。。。可以计算加权图上的最短路径。此外，我假设使用未加权图来表示具有负边的加权图是非常困难的。