Combinatorial optimization-typical problem-shortest path problem

Typical problem and execution method

Shortest path problem

When $ e_ {ij} = (v_i, v_j) \ in E $ has a weight of $ a_ {ij} $ on each side of the graph $ G = (V, E) $, the start point $ v_s \ in V $ to the end point $ Find the one with the smallest sum of weights on the way to v_t \ in V $.

Execution method

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 data
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))

result


[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


#Random number data
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.26, 1)
print(nx.dijkstra_path(g, 0, 2))

result


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

dij.png

data

Recommended Posts

Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-typical problems and execution methods