Генерация кратчайшего пути с ровно k ребрами в ориентированном и взвешенном графике (редактирование: посещение каждого узла только один раз)

Question

Этот следующий код от https://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/. Все кредиты идут в PranchalK.

Я имею дело с проблемой генерации кратчайшего пути по k-краю.Приведенный ниже код дает кратчайшее «расстояние» с предопределенным значением k.
Однако мне понадобится «путь». Для кода ниже путь выглядит следующим образом:
0 -> 2 -> 3.
Edit: код Ajay решает эту проблему.Однако каждый узел необходимо посетить только один раз.Я не упоминал об этом в первоначальном вопросе.Я включил дополнительный набор данных, чтобы проверить это.

# Python3 program to find shortest path 
# with exactly k edges 

# Define number of vertices in the graph 
# and inifinite value 

# A naive recursive function to count 
# walks from u to v with k edges 
def shortestPath(graph, u, v, k): 
    V = 4
    INF = 999999999999

    # Base cases 
    if k == 0 and u == v: 
        return 0
    if k == 1 and graph[u][v] != INF: 
        return graph[u][v] 
    if k <= 0: 
        return INF 

# Initialize result 
    res = INF 

# Go to all adjacents of u and recur 
    for i in range(V): 
        if graph[u][i] != INF and u != i and v != i: 
            rec_res = shortestPath(graph, i, v, k - 1) 
            if rec_res != INF: 
                res = min(res, graph[u][i] + rec_res) 
    return res 

# Driver Code 
if __name__ == '__main__': 
    INF = 999999999999

    # Let us create the graph shown 
    # in above diagram 
    graph = [[0, 10, 3, 2], 
            [INF, 0, INF, 7], 
            [INF, INF, 0, 6], 
            [INF, INF, INF, 0]] 
    u = 0
    v = 3
    k = 2
    print("Weight of the shortest path is", 
            shortestPath(graph, u, v, k)) 

# This code is contributed by PranchalK 

Ожидаемый результат:
[0,2,3]

0 - начальный узел, 3 - конечный узел.Число ребер равно 2. Путь 0 -> 2 -> 3

Правка: ответ Аджая очень и очень близок.Однако каждый узел необходимо посетить только один раз.Мне жаль, что я не упомянул об этом изначально.Вот большие данные для тестирования.

    graph = [[0, 10, 3, 2,4,1],
            [1, 0, 3, 7,4,1],
            [2, 8, 0, 6,0,1],
            [4, 1, 3, 0,1,2],
            [3, 1, 2, 2,4,1],
            [7, 1, 3, 0,3,3]] 

Weight of the shortest path is 14
Shortest path is  [0, 2, 0, 2, 3]

Answer 1

Проверяя существующие алгоритмы NetworkX в Кратчайшие пути , кажется, что ни один из них не позволяет напрямую получить все простые пути между двумя узлами и вместе с соответствующими весами.

Так что будет необходимо выполнить обе вещи по отдельности:

• Вычислить все пути между двумя заданными узлами и сохранить только те из них, которые имеют длину k
• Изатем вычислите вес каждого из этих индивидуальных путей и выберите один из путей с меньшим весом

---

Общее решение

def shortest_path_k_edges(graph, source, target, k):
    '''
    Computes the shortest simple path with
    exactly k edges of a weighted graph 
    between the specified source and target
    ----
    graph: np.array
       Adjacency matrix for the graph
    source: int
       Source node
    target: int
       Target node
    k: int
       Amount of edges of the path
    ----       
    Returns:
       Shortest k length path    
    '''
    import networkx as nx
    # Builds graph from the adjacency matrix
    g = nx.from_numpy_array(graph)
    # Generates all simple paths (no repeated nodes) 
    # in the graph from source to target
    all_paths = nx.all_simple_paths(g, source, target)
    # Keeps only paths with k edges
    paths = [i for i in all_paths if len(i) == k+1]
    # Compute the weights of each of the paths
    # using the adjacency matrix
    weights = [sum(graph[i[j], i[j+1]] 
                   for j in range(len(i)-1)) 
               for i in paths]
    # Return path of minimum weight, and
    # corresponding weight
    min_w = min(weights)
    return paths[weights.index(min_w)], min_w

---

Вывод

Позволяет проверить результаты с предлагаемыми параметрами:

u = 0
v = 3
k = 2
INF = 999999999999
import numpy as np
graph = np.array(
       [[0, 10, 3, 2], 
        [INF, 0, INF, 7], 
        [INF, INF, 0, 6], 
        [INF, INF, INF, 0]])

path, weight = shortest_path_k_edges(graph, u, v, k)

print(path)
# [0, 2, 3]

print(weight)
# 9

Answer 2

Хранить узел, который дает мин.сумма веса для каждой длины ребра

def shortestPath(graph, u, v, k):
    V = 4
    INF = 999999999999

    # Base cases
    if k == 0 and u == v:
        return 0,[]
    if k == 1 and graph[u][v] != INF:
        return graph[u][v],[]
    if k <= 0:
        return INF,[]

# Initialize result
    res = INF

# Go to all adjacents of u and recur
    k_minus_one_path = []
    least_sum_node = None
    for i in range(V):
        if graph[u][i] != INF and u != i and v != i:
            rec_res, path = shortestPath(graph, i, v, k - 1)
            if rec_res != INF:
                if res > graph[u][i] + rec_res:
                    k_minus_one_path = path
                    least_sum_node = i
                    res = graph[u][i] + rec_res

    if least_sum_node is not None:
        k_minus_one_path.insert(0, least_sum_node)

    k_path = k_minus_one_path

    return res,k_path

# Driver Code
if __name__ == '__main__':
    INF = 999999999999

    # Let us create the graph shown
    # in above diagram
    graph = [[0, 10, 3, 2],
            [INF, 0, INF, 7],
            [INF, INF, 0, 6],
            [INF, INF, INF, 0]]
    u = 0
    v = 3
    k = 2
    weight, path = shortestPath(graph, u, v, k)
    if weight != INF:
        path.insert(0, u)  # source
        path.append(v)  # Destination
    print("Weight of the shortest path is", weight)
    print("Shortest path is ", path)