请问各位，对于含负权回路的无向图，最短路问题如何用python解决？（希望有具体的代码）
存在负权回路的图是不能求两点间最短路的，因为在负权回路上不断兜圈子所得的最短路长度可以无限小。
除非把题目改成:求连接两点间权重最小的路(每个点不重复经过)
实现代码：paths_result 包含2点之间（a, c为例）的所有路径 及权值和，比较大小取最小的 -3 即可
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Description: todo
Author: gnn
Date: 2022/12/12
"""
# 如何运用深度遍历算法，输入始发点，目的点，最大步长，得出俩点间的所有路径？
# 例：输入始发点A，目的点F，步长4，得出路径A-B-F、A-C-F、A-E-K-F
# 输入始发点A，目的点F，步长3，得出路径A-B-F、A-C-F
# 输入始发点A，目的点C，步长任意，得出路径A-C
# 定义字典，表示该节点与其他节点的连通关系
from itertools import groupby
def findAllPath(graph, start, end, path=[]):
# path.append(start)
path = path + [start]
if start == end:
return path
for node in graph[start]:
if node not in path:
newpaths = findAllPath(graph, node, end, path)
for newpath in newpaths:
if newpath == end:
path.append(newpath)
paths.append(path)
return paths
def get_graph(graph_dict):
# 打散, 获取相关的两个点
t = [(kvs[0], v) for kvs in graph_dict.items() for vs in kvs[1] for v in vs]
# 反转两个点, 获取2个点的相互关系
t_re = [(t2[1], t2[0]) for t2 in t]
t.extend(t_re)
# 聚合得到每个点的下个点
t_g = groupby(sorted(t, key=lambda x: x[0]), key=lambda x: x[0])
# 每个点的所有直接连接点
t_dict = {k: [v[1] for v in list(vs)] for k, vs in t_g}
return t_dict
if __name__ == '__main__':
# 图 连接点
graph = {
'a': ['b', 'c', 'd'],
'b': ['c', 'd'],
'c': ['d', 'e'],
'd': ['e'],
'e': ['b', 'd']
}
# 权 以 a 到 c 为例, 其他点需要补充
quan = {
'a-b': -5,
'b-c': 2,
'a-c': 9
}
t_dict = get_graph(graph)
start, end = 'a', 'c'
paths = [] # 存储所有路径
findAllPath(t_dict, start, end)
paths_result=[]
for vs in paths:
len_sum = 0
for i, v in enumerate(vs):
if i < len(vs)-1:
len_sum += quan.get(f'{vs[i]}-{vs[i+1]}')
paths_result.append(["-".join(vs), len_sum])
print(f'start: {start}, end: {end}, result: {paths_result}')
运行结果：
start: a, end: c, result: [['a-b-c', -3], ['a-c', 9]]
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
/*
* 求解无向图的单源最短路径
*/
public class NonDirectedGraph {
private class Vertex{
private String vertexLabel;//顶点标识
private List<Edge> adjEdges;//与该顶点邻接的边(点)
private int dist;//顶点距离(该顶点到起始顶点的距离)
private Vertex preNode;
public Vertex(String vertexLabel) {
this.vertexLabel = vertexLabel;
adjEdges = new LinkedList<>();
dist = Integer.MAX_VALUE;
preNode = null;
}
}
private class Edge{
private Vertex endVertex;
public Edge(Vertex endVertex) {
this.endVertex = endVertex;
}
}
private Map<String, Vertex> nonDirectedGraph;//保存了图中所有的顶点，边的关系以List形式保存在Vertex类中
private Vertex startVertex;//图的起始顶点
public NonDirectedGraph(String graphContent) {
nonDirectedGraph = new LinkedHashMap<>();
buildGraph(graphContent);
}
private void buildGraph(String graphContent){
String[] lines = graphContent.split("\n");
String startNodeLabel, endNodeLabel;
Vertex startNode, endNode;
for(int i = 0; i < lines.length; i++){
String[] nodesInfo = lines[i].split(",");
startNodeLabel = nodesInfo[1];
endNodeLabel = nodesInfo[2];
endNode = nonDirectedGraph.get(endNodeLabel);
if(endNode == null){
endNode = new Vertex(endNodeLabel);
nonDirectedGraph.put(endNodeLabel, endNode);
}
startNode = nonDirectedGraph.get(startNodeLabel);
if(startNode == null){
startNode = new Vertex(startNodeLabel);
nonDirectedGraph.put(startNodeLabel, startNode);
}
Edge e = new Edge(endNode);
//对于无向图而言,起点和终点都要添加边
endNode.adjEdges.add(e);
startNode.adjEdges.add(e);
}
startVertex = nonDirectedGraph.get(lines[0].split(",")[1]);//总是以文件中第一行第二列的那个标识顶点作为源点
}
public void unweightedShortestPath(){
unweightedShortestPath(startVertex);
}
/*
* 计算源点s到无向图中各个顶点的最短路径
* 需要一个队列来保存图中的顶点,初始时,源点入队列,然后以广度的形式向外扩散求解其他顶点的最短路径
*/
private void unweightedShortestPath(Vertex s){
//初始化
Queue<Vertex> queue = new LinkedList<>();
s.dist = 0;
queue.offer(s);//将源点dist设置为0并入队列
while(!queue.isEmpty()){
Vertex v = queue.poll();
for (Edge e : v.adjEdges) {//扫描v的邻接边(点)
if(e.endVertex.dist == Integer.MAX_VALUE){//如果这个顶点(e.endVertex)未被访问(每个顶点只会入队列一次)
e.endVertex.dist = v.dist + 1;//更新该顶点到源点的距离
queue.offer(e.endVertex);
e.endVertex.preNode = v;//设置该顶点的前驱顶点
}//end if
}//end for
}//end while
}
//打印图中所有顶点到源点的距离及路径
public void showDistance(){
Collection<Vertex> vertexs = nonDirectedGraph.values();
for (Vertex vertex : vertexs) {
System.out.print(vertex.vertexLabel + "<--");
Vertex tmpPreNode = vertex.preNode;
while(tmpPreNode != null){
System.out.print(tmpPreNode.vertexLabel + "<--");
tmpPreNode = tmpPreNode.preNode;
}
System.out.println("distance=" + vertex.dist);
}
}
}
带负权回路无向图，就需要规定各个点经过的次数，否则就无法求最小值