如何在特殊矩阵中使用scipy的dijkstra函数?

iq3niunx  于 2022-11-23  发布在  其他
关注(0)|答案(1)|浏览(138)

我有一些代码可以把一个未加权的图转换成一个加权的图其中一些节点的权重为1,一些节点的权重为0。最终结果是一个矩阵。我想知道如何在Djikstra scipy实现中使用这个矩阵,但我并不完全了解documentation,而且周围也没有很多对begginer友好的资源,所以我不知道该怎么做。下面是库中djikstra代码的实现

def dijkstra_algorithm(matrix, s_id, t_id):
    scipy.sparse.csgraph.dijkstra(matrix)

这是创建有权重和无权重矩阵的代码

def read_special_graph():
    node_ids = {}

    counter = 0
    for node in nodes:
        node_ids[node] = counter
        counter += 1

    matrix = [[float("inf")]*len(nodes) for _ in range(len(nodes))]

    s_id = node_ids[s.id]
    t_id = node_ids[t.id]
    for node in nodes:
        node_id = node_ids[node.id]
        for out_node in node.out_edges:
            out_id = node_ids[out_node.id]
            if out_node.red:   
                matrix[node_id][out_id] = 1
            else:   
                matrix[node_id][out_id] = 0
    
    dijkstra_algorithm(matrix, s_id, t_id)

我没有错误消息,因为我还没有运行它,我只是不知道我应该做什么与我的情况。
我已经编写了不同的代码来解析节点来自的一些文件。

7uhlpewt

7uhlpewt1#

该函数将计算完整的距离矩阵,因此您可以使用

def dijkstra_algorithm(matrix, s_id, t_id):
    transitive_matrix = scipy.sparse.csgraph.dijkstra(matrix)
    return transitive_matrix[s_id, t_id]

它提到了使用Fibonacci堆(我假设是python堆)的dijkstra算法,所以我想使用其他方法可以更快地计算它。

相关问题