조합 최적화 - 일반적인 문제 - 최단 경로 문제

일반적인 문제와 실행 방법

최단로 문제

그래프 $G=(V,E)$의 각 변 $e_{ij}=(v_i,v_j)\in E$가 가중치 $a_{ij}$를 가질 때 시작점 $v_s\in V$에서 끝점$ v_t\in V$로 가는 길에서 가장 가중치가 작은 것을 찾습니다.

실행 방법

usage

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

파이썬

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

결과

[5, 4, 0, 2]

파이썬

# 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



파이썬

# 乱数データ
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.26, 1)
print(nx.dijkstra_path(g, 0, 2))

결과

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

데이터

data/node0.csv

data/edge0.csv