Combinaison d'optimisation-problème typique-problème de chemin le plus court

Problème typique et méthode d'exécution

Problème routier le plus court

Lorsque $ e_ {ij} = (v_i, v_j) \ in E $ a un poids de $ a_ {ij} $ de chaque côté du graphe $ G = (V, E) $, le point de départ $ v_s \ in V $ jusqu'au point final $ Trouvez celui avec la plus petite somme de poids sur le chemin de v_t \ dans V $.

Méthode d'exécution

usage

Signature: nx.dijkstra_path(G, source, target, weight='weight')
Docstring:
Returns the shortest path from source to target in a weighted graph G.

python

#Données CSV
import pandas as pd, networkx as nx
from ortoolpy import graph_from_table
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
print(nx.dijkstra_path(g, 5, 2))

résultat

[5, 4, 0, 2]

python

# pandas.DataFrame
from ortoolpy.optimization import DijkstraPath
DijkstraPath('data/edge0.csv', 5, 2)

python

#Données aléatoires
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.26, 1)
print(nx.dijkstra_path(g, 0, 2))

résultat

[0, 1, 6, 3, 5, 2]

Les données

• data/node0.csv
• data/edge0.csv