#coding:utf-8
### Bellman-Fordのアルゴリズム 最短経路探索
### for Suumer Research 2018
### author Daiki Shimizu
### 20180626暫定

### cf.) https://gist.github.com/joninvski/701720
### 経路を出力できるようにしたので，あとは隣接行列を読み込めるようにする．
### csv→辞書型への変換

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

import pdb
"""
The Bellman-Ford algorithm
Graph API:
    iter(graph) gives all nodes
    iter(graph[u]) gives neighbours of u
    graph[u][v] gives weight of edge (u, v)
"""

import time

start_time = time.time()

#d = {}
#while
#    d.['i'] = dd

# pandasを用いてcsvを読み込み
import pandas as pd
lst = pd.read_csv("C:/Users/deded/Documents/tansaku/shibuyamatrix.csv", header=None).values.tolist()

# 辞書in辞書の型を作成
i = 1
d = {}
dd = {}
while i <= len(lst):
    d[str(i)] = dd
    i += 1

m = 0
while m <= len(lst)-1:
    dd={}
    n = 0
    while n <= len(lst)-1:
        if lst[m][n] != 0:
            dd[str(n+1)] = lst[m][n]
        #if lst[m][n] == 0:
            #pass
        n += 1
    d[str(m+1)] = dd
    m += 1

#for m in range(len(lst)):
#    for n in range(len(lst)):
#        if lst[m][n] != 0
#            dd[n+1] = lst[m][n]
#            print(dd)
#        else:
#            pass



 #   if lst[m][n] == 0:
 #       pass
 #   if m > len(lst):
 #       break
 #   dd[m] = lst[m][n]
 #   m += 1
 #   n += 1



"""
graph1 = {
        '1': {'2': -1, '3':  4},
        '2': {'3':  3, '4':  2, '5':  2},
        '3': {},
        '4': {'2':  1, '3':  5},
        '5': {'4': -3}
        }
"""

# Step 1: For each node prepare the destination and predecessor
def initialize(graph, source):
    d = {}  # Stands for destination
    p = {}  # Stands for predecessor
    for node in graph:
        d[node] = float('Inf')  # We start admitting that the rest of nodes are very very far
        p[node] = None
    d[source] = 0  # For the source we know how to reach
    return d, p

def relax(node, neighbour, graph, d, p):
    # If the distance between the node and the neighbour is lower than the one I have now
    if d[neighbour] > d[node] + graph[node][neighbour]:
        # Record this lower distance
        d[neighbour] = d[node] + graph[node][neighbour]
        p[neighbour] = node

def bellman_ford(graph, source, goal):
    d, p = initialize(graph, source)
    for i in range(len(graph)-1):  # Run this until is converges
        for u in graph:
            for v in graph[u]:  # For each neighbour of u
                relax(u, v, graph, d, p)  # Lets relax it

    # Step 3: check for negative-weight cycles
    for u in graph:
        for v in graph[u]:
            assert d[v] <= d[u] + graph[u][v]

    i = goal
    l = []
    while True:
        if i == source:
            break
        l.insert(0,i)
        i = p[i]
    l.insert(0,source)

    print ("(出発地，到着地，最短距離，経路)")
    return source,goal,d[goal],l



print(bellman_ford(d,'562','1354'))
#print(lst)
#print(d)

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