[PYTHON] Kombinationsoptimierung - typisches Problem - Problem mit dem kürzesten Weg
Typisches Problem und Ausführungsmethode
Kürzestes Straßenproblem
Wenn jede Seite $ e_ {ij} = (v_i, v_j) \ in E $ des Graphen $ G = (V, E) $ ein Gewicht von $ a_ {ij} $ hat, ist der Startpunkt $ v_s \ in V $ bis zum Endpunkt $ Finden Sie die mit der kleinsten Summe von Gewichten auf dem Weg zu v_t \ in V $.
Ausführungsmethode
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
#CSV-Daten
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))
Ergebnis
[5, 4, 0, 2]
python
# pandas.DataFrame
from ortoolpy.optimization import DijkstraPath
DijkstraPath('data/edge0.csv', 5, 2)
| node1 | node2 | capacity | weight | |
|---|---|---|---|---|
| 9 | 4 | 5 | 2 | 1 |
| 3 | 0 | 4 | 2 | 2 |
| 1 | 0 | 2 | 2 | 4 |
python
#Zufällige Daten
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.26, 1)
print(nx.dijkstra_path(g, 0, 2))
Ergebnis
[0, 1, 6, 3, 5, 2]
Daten
Recommended Posts