Dijkstra Algorithm



#Abstract
 Dijkstra Algorithm[^1] is an algorithm for finding the shortest paths between nodes in a graph. It is well-known among Japanese science undergraduate students, for it is always taught as mathematical optimization. However, it is taught just a method by hand, not programming. So I will program it in order to review it in Python.

#Order
 Dijkstra Algorithm Order $O((|V|+|E|)\log |V|)$ (where $|V|$ is the number of nodes and $|E|$ is the number of edges).

#Aim
- input
    - start place and goal place
    - the number of nodes and edges (from the text)
    - weight and a path pair for an arbitrary edge (from the text)
- output
    - how to route
    - what weight

#Programming
I use the heap queue algorithm[^2]. The interesting property of a heap is that its smallest element is always the root, heap[0]. I referred to a code from this site[^3]. Thanks.

```djk.py
from heapq import heappush, heappop

INF=10**10

start,goal=map(int,input().split())

###　Directly Input
'''
e,v=map(int,input().split())

edge=[[] for _ in range(v)]
#edge[place] : information list of path from place.

for i in range(e):
    a_place,b_place,cost=map(int,input().split())
    edge[a_place].append((b_place,cost))
    edge[b_place].append((a_place,cost))
'''
###

### Indirectly From Text

f = open('sample.txt', 'r')
datalist= f.readlines()

e,v=map(int,datalist[0].split())
edge=[[] for _ in range(v)]
for i in range(e):
    a_place,b_place,cost=map(int,datalist[i+1].split())
    edge[a_place].append((b_place,cost))
    edge[b_place].append((a_place,cost))
###

def dijkstra(s,g,n): #(start,goal,number of nodes)
    # Mark all nodes unvisited
    Visited=[False]*n
    # Assign to every node a tentative distance value
    dist=[INF]*n
    # Are you from?
    birth_place=[-1]*n

    hq=[(0,s)] # Research target (distance, node)
    dist[s]=0
    birth_place[s]=s
    while hq and (Visited[g]==False):
        distance, node = heappop(hq)
        Visited[node]=True
        for next_place, weight in edge[node]:
            if Visited[next_place]== False and distance + weight < dist[next_place]:
                dist[next_place] = distance + weight
                birth_place[next_place]=node
                heappush(hq,(dist[next_place],next_place))
    
    return dist[g],birth_place

cost,djk=dijkstra(start,goal,v)

route=[goal]
t=goal

while t!=start:
    route.append(djk[t])
    t=djk[t]

print('Route : ', end='')
for i in range(len(route)):
    if i != len(route)-1:
        print(route[len(route)-1-i], end='->')
    else:
        print(route[len(route)-1-i])

print('Cost : ', end='')
print(cost)

```

```sample.txt
5 4
0 1 1
0 2 2
1 2 10
1 3 8
2 3 5
```
![djk.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/417525/af067f68-5475-7ffb-2055-31e9f48e3b0e.png)


```terminal
$python3 djk.py
0 3
Route : 0->2->3
Cost : 7
```

#Future Tasks
- Random Generation of undirected graphs
- Consider how a transfer navigation app([^4],[^5],etc.) is created and improve
    - Search range
    - Commuter pass information
    - Time constraint
    - A money System
    - Lines System
 
#Homeworks
Improve djk.py
1. to answer all, if there are multiple answers.
2. to apply for future tasks

[^1]: Wikipedia https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (7th Feb 2021)

[^2]: Heap queue algorithm https://docs.python.org/3/library/heapq.html (7th Feb 2021)

[^3]: 単一始点最短経路問題を Dijkstra 法で実装する in Python https://mirucacule.hatenablog.com/entry/2020/05/21/124026 

[^4]: Yahoo! 路線情報 https://transit.yahoo.co.jp/ (7th Feb 2021)

[^5]: 駅すぱあと for WEB https://roote.ekispert.net/ja/ (7th Feb 2021)