### Dijkstraのアルゴリズム 最短経路探索
### for BinN start up seminar 2018
### author Mizuki UEDA
### 20180416

### cf.) FUKUDA LAB. http://www.plan.cv.titech.ac.jp/fukudalab/research/lab-seminar/
### 2017年12月閲覧 参考にさせていただきました

###################################################
###パッケージの読み込み######
###################################################

import numpy as np
from scipy.stats import rankdata
#from numpy import *
import pandas as pd
import itertools
import math
import heapq
import time

start_time = time.time()

###################################################
###データ読み込み######
###################################################

# ラベル付き隣接行列: 得られたデータを書き込んでください！
"""
m = [
    [0, 142.2064614, 0, 89.68804473, 0, 0, 0, 0, 0],
    [142.2064614, 0, 314.46613, 0, 204.8164485, 0, 0, 0, 0],
    [0, 314.46613, 0, 0, 0, 81.37164805, 0, 0, 0],
    [89.68804473, 0, 0, 0, 287.8825196, 0, 373.8821118, 0, 0],
    [0, 204.8164485, 0, 287.8825196, 0, 201.4898183, 0, 502.5906807, 0],
    [0, 0, 81.3716480459089, 0, 201.4898183, 0, 0, 0, 496.0501523],
    [0, 0, 0, 373.8821118, 0, 0, 0, 239.2130025, 0],
    [0, 0, 0, 0, 502.5906807, 0, 239.2130025, 0, 129.1523508],
    [0, 0, 0, 0, 0, 496.0501523, 0, 129.1523508, 0],
]
"""
# csvに書き込んでもよいです 量が多いときはこれ自体をコード書いて処理してつくるのがよいでしょう
m = np.genfromtxt( "C:/Users/deded/Documents/tansaku/shibuyamatrix.csv", delimiter="," , filling_values=(0) )



OD = pd.DataFrame(np.loadtxt( "C:/Users/deded/Documents/tansaku/OD.csv", delimiter="," ,skiprows=1))
OD.columns = ["O", "D"]

Olist = OD['O']
Dlist = OD['D']

###################################################
###定義######
###################################################

# ネットワークｍにおいて出発地startから目的地goalまでの最短経路を探していきます


def dijkstra(m, start, goal=None):

    num = len(m)  # グラフのノード数

    dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する

    prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

    dist[start] = 0

    q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル

    heapq.heappush(q, (0, start))  # 始点をpush

    while len(q) != 0:

        prov_cost, src = heapq.heappop(q)  # pop

        # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない

        if dist[src] < prov_cost:
            continue

        # 他の頂点の探索

        for dest in range(num):

            cost = m[src][dest]

            if cost != 0 and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost  # distの更新

                heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush

                prev[dest] = src  # 前の頂点を記録

    if goal is not None:

        return (get_path(goal, prev), dist[goal])

    else:

        return dist

def get_path(goal, prev):

    path = [goal+1]  # 最短経路

    dest = goal

    # 終点から最短経路を逆順に辿る

    while prev[dest] != float('inf'):
        path.append(prev[dest]+1)

        dest = prev[dest]

    # 経路をreverseして出力

    return list(reversed(path))


for v in range(len(Olist)):

    origin = int(Olist[v])-1
    destination = int(Dlist[v])-1

    print(origin + 1, destination + 1)


    print(dijkstra(m, origin, destination))

execution_time = time.time() - start_time
print(execution_time)