为何Networkx的Dijkstra算法比Boost的更快？

我最初用Python的NetworkX库实现Dijkstra算法，为提升性能改用C的Boost图库，却意外发现Python版本的最短路径计算速度反而更快。我是C新手，不确定是否存在实现问题，以下是复现问题的示例代码及编译配置，希望有人帮忙验证是否仅我遇到此问题。

Python代码 #

import networkx as nx
import csv
import time
import numpy as np

def write_graph_to_csv(G):
    # Open a CSV file in write mode
    with open('/Users/robertbenassai/Documents/UOC/k_shortest_path_betweenness/KSP_cpp/graph.csv', 
              'w', newline='') as csvfile:
        # Create a CSV writer object
        csvwriter = csv.writer(csvfile)
    
        # Write the header row (optional)
        csvwriter.writerow(['vertex1', 'vertex2', 'edge_weight'])
    
        # Write edges and their weights to the CSV file
        for u, v, weight in G.edges(data='length'):
            csvwriter.writerow([u, v, weight])

    print('Graph has been written to graph.csv')


graph = nx.random_geometric_graph(100, 0.2)
pos_RG = nx.get_node_attributes(graph, 'pos')
edge_lens = {edge: np.linalg.norm(np.array(pos_RG[edge[1]]) - np.array(pos_RG[edge[0]])) for edge 
              in graph.edges}

nx.set_edge_attributes(graph, edge_lens, name = "length")

nx.draw_networkx(graph, pos_RG)


times_del = []
for i in range(100):
    t1 = time.time()
    nx.single_source_dijkstra(graph, 1, weight = "length")
    times_del.append(time.time()-t1)
    # print(time.time()-t1)
print(np.mean(times_del))

write_graph_to_csv(graph)

C++代码 #

#include <iostream>
#include <vector>
#include <chrono>
#include <numeric>

#include <boost/property_map/dynamic_property_map.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/tokenizer.hpp>

using namespace boost;
using namespace std::chrono;

struct NodeProperties {
    int id;

};

typedef boost::adjacency_list<
    boost::listS,                
    boost::vecS,                 
    boost::undirectedS,          
    NodeProperties,              
    boost::property<boost::edge_weight_t, double> 
> Graph;

// typedef adjacency_list<listS, vecS, undirectedS,
//     no_property, property<edge_weight_t, double> > Graph; 

typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;
typedef std::pair<int, int> EdgePair;

int main() {

    /*
    
    READING CSV FILE: EDGE[0], EDGE[1], WEIGHT

    */

    Graph delaunay(0);

    std::ifstream file("graph.csv");
    std::string line;
    std::getline(file, line);

    while (std::getline(file, line)) {
        boost::tokenizer<boost::escaped_list_separator<char>> tokens(line);
        auto tokenIterator = tokens.begin();
        int vertex1 = std::stoi(*tokenIterator++);
        int vertex2 = std::stoi(*tokenIterator++);
        double weight = std::stod(*tokenIterator);
        // Add edge to the graph with the given weight
        Edge e = add_edge(vertex1, vertex2, delaunay).first;
        put(edge_weight, delaunay, e, weight);
        // boost::add_edge(vertex1, vertex2, EdgeProperties{weight}, delaunay);
    }


    std::vector<int> path(num_vertices(delaunay), -1);  // Initialize path with -1 for all vertices
    std::vector<double> distances(num_vertices(delaunay));  // Store distances for Dijkstra's algorithm
    std::vector<double> times(100);
    for (int i = 0; 100>i; i++){
        auto t1 = high_resolution_clock::now();

        boost::dijkstra_shortest_paths(delaunay, 1,
                                    predecessor_map(make_iterator_property_map(path.begin(), get(vertex_index, delaunay)))
                                    .distance_map(make_iterator_property_map(distances.begin(), get(vertex_index, delaunay))));
        
        auto t2 = high_resolution_clock::now();
        std::chrono::duration<float> deltat = (t2 - t1);
        std::cout << "Dijkstra time: "
        << deltat.count() << " seconds" << std::endl;
        times[i] = deltat.count();
    }
    double mean_t = std::accumulate(times.begin(), times.end(), 0.0) / times.size();
    printf("mean time: %lf", mean_t);
    return 0;
}

编译配置（Makefile） #

INC_DIRS = /opt/homebrew/include
LIB_DIRS = /opt/homebrew/lib

CPPFLAGS += -std=c++17

# Link igraph and other libraries
LDFLAGS = -ligraph -lboost_filesystem -lboost_graph

Yen: k_shortest_paths.cpp
    $(CXX) $(CFLAGS) $(CPPFLAGS) -I$(INC_DIRS) -L$(LIB_DIRS) $(LDFLAGS) $< -o $@

clean:
    rm Yen

内容的提问来源于stack exchange，提问作者Robert Benassai