Вычислить кратчайший маршрут подмножества графа - PullRequest
Новая
       94

Вычислить кратчайший маршрут подмножества графа

1 голос
/ 29 мая 2020

Я пытаюсь вычислить кратчайшее расстояние между подмножеством этого графика: 

graph = {'a': {'b':10, 'c':3}, 'b':{'c':1, 'd':2}, 'c':{'b':4, 'd':8, 'e':2}, 'd':{'e':7}, 'e':{'d':9}}

Я пытаюсь использовать алгоритм Дейкстры, но не уверен, как именно преобразовать его в приведенное выше:

Текущий код: 

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}}

def dijkstra(graph, start, goal):
    shortest_distance = {}
    predecessor = {}
    unseenNodes = {'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}}
    infinity = float('inf')
    path = []

    for node in unseenNodes:
        shortest_distance[node] = infinity
    shortest_distance[start] = 0
    #print(shortest_distance)

    while unseenNodes:
        minNode = None
        for node in unseenNodes:
            if minNode is None:
                minNode = node
            elif shortest_distance[node] < shortest_distance[minNode]:
                minNode = node
        for childNode, weight in graph[minNode].items():
            if weight + shortest_distance[minNode] < shortest_distance[childNode]:
                shortest_distance[childNode] = weight + shortest_distance[minNode]
                predecessor[childNode] = minNode
        unseenNodes.pop(minNode)

    currentNode = goal
    while currentNode != start:
        try:
            path.insert(0, currentNode)
            currentNode = predecessor[currentNode]
        except KeyError:
            print('Path not reachable')
            break
    path.insert(0, start)

    if shortest_distance[goal] != infinity:
        print('Shortest distance: ' + str(shortest_distance[goal]))
        print('Path:' + str(path))

def multi_dijkstra(*args):
    # TODO: run dijkstra function for each: X
    # TODO: Add trip to 2nd (or3rd/4th) node back L1
    for args in args:
        dijkstra(graph, args, 'L1')
        dijkstra(graph, 'L1', args[])

    # print total cost

    # print total distance
    #print(args)

#dijkstra(graph, 'L1', 'c2')
#dijkstra(graph, 'c2', 'c3')
multi_dijkstra('c1', 'c2')

Маршрут может начинаться в любой точке, но должен заканчиваться sh на L1. Например c2 (начало) -> c1 -> L1 (fini sh).

1 Ответ

1 голос
/ 29 мая 2020

Можно использовать Python модуль NetworkX: 

from networkx import DiGraph
from networkx.algorithms.shortest_paths.generic import shortest_path

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: ['c1', 'L1', 'c3']
...