PyCPXで最短路問題を解く

pycpx_shortest_distance.py

# -*- coding: utf-8 -*-

import numpy as np
from pycpx import CPlexModel

# 入力（有向グラフ，頂点は0-index）
# n m
# s_1 t_1 c_1
# s_2 t_2 c_2
# ...
# s_m t_m c_m

n, m = map(int, raw_input().split())

model = CPlexModel()
d = model.new(n)
model.constrain(d[0] == 0)
for i in range(m):
        s, t, c = map(int, raw_input().split())
        model.constrain(d[t] <= d[s] + c)

model.maximize(d[n-1])
print model[d]

# 4 5
# 0 1 1
# 0 2 4
# 1 2 2
# 2 3 1
# 1 3 5
# -> [ 0.  1.  3.  4.]