Dijkstra Algorithm

Abstract

Dijkstra Algorithm¹ 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². 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³. 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

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

Future Tasks

• Random Generation of undirected graphs
• Consider how a transfer navigation app(⁴,⁵,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) ↩