We are wanting to identify shortest path in a small network (10 nodes). It is weighted, positive and negative edges, and non-directed. We understand Dijkstra con’t work, so tried Bellman Ford but it appears cos there are negative weights and undirected, this porduces a negative cycle which BFA cannot deal with.
ChatGPT recommended we use Python - can we get that verified please?
The classic shortest path problem with negative weights is not meaningful in undirected networks, as you can make the path length arbitrarily low (i.e. arbitrarily high-magnitude negative) by traversing a negative weight edge multiple times.
You can look into the longest path problem (with negated weights) where the customary definition forbids repeated vertices. This, however, makes the problem NP-hard. igraph does not have a longest path implementation at this moment.