I am trying to find the shortest path that travels through specified nodes in a graph (A -> B -> C instead of just A -> C). Currently, my code will return the shortest path rather than going through all specified nodes.
Code:
from networkx import DiGraph
from networkx.algorithms.shortest_paths import multi_source_dijkstra
graph = {'c1': {'c2': 4, 'L1': 3},
'c2': {'c1': 4, 'c3': 3, 'L1': 2.5},
'c3': {'c2': 3, 'L1': 2},
'L1': {'c1': 3, 'c2': 2.5, 'c3': 2}}
# Build the graph
G = DiGraph()
G.add_weighted_edges_from(((source, target, weight)
for source, d in graph.items()
for target, weight in d.items()))
# Find shortest path (using Dijkstra algorithm)
#result = shortest_path(G, source='c1', target='c3', weight='weight')
result = multi_source_dijkstra(G, sources=['c2','c3'], target='L1')
print(result)
# result: (2, ['c3', 'L1'])
Library and function I am using: https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path
I noticed networkx have two traveling salesman functions, but neither of them can return the path, only the distance so I don't think I can use them.
You should make multiple calls of shortest_path, one for each subpath you need. So when the request is A->B->C, then find the shortest path from A to B, and the one from B to C and concatenate the two results.
multi_source_dijkstra does something different: it finds a path from one of the source nodes to the target node.