Ch8-Shortest path algorithm for coding test

1. Shortest path algorithm
2. Dijkstra algorithm
3. Implement basic Dijkstra algorithm
4. Implement advanced Dijkstra algorithm
5. Floyd-Warshall algorithm

Q1. Future city

Q2. Send a telegram

1. Shortest path algorithm

There are many type of shortest path algorithm and the way to use these algorithm in specific condition are already established. For example, it’s like ‘Find the shortest path from one point to another specific point’, ‘Find every shortest path from every points to every points’. Most principle algorithm in undergraduate CS level is ‘Dijkstra algorithm’, ‘Floyd-warshall algorithm’ and ‘Bellman-Ford algorithm’. ‘Dijkstra’ and ‘Floyd-warshall’ are commonly used in coding test so it is no problem that is study two algorithms. Greedy algorithm and Dynamic programming are used in these shortest path algorithms.

2. Dijkstras algorithm

Dijkstras algorithm is shortest path algorithm to find several nodes in graph, starting form specific node to other nodes. It works when there are no negative weight edges. Negative weight edges means the edges which has under the zero value. This is not exist in the reality so it is used in GPS software.

Dijkstras algorithm is classified in greedy algorithm because it repeats the process to find lowest cost of nodes. The process is like these.

1. Define starting node
2. Initialize shortest path table
3. Choose shortest path node which is not marked a visit
4. Calculate the cost to move from specific node to other node and update the shortest path table
5. Repeat the process 3,4

It has the feature which is updating the 1-dimension list to store information of shortest path distance from specific node to each nodes. The guy who prepare coding test need to exactly know this Dijkstras algorithm and there are many high level problems using Dijkstras algorithm so it will be help when you solve this problems.

Let’s look at principle of Dijkstra algorithm. Find the shortest path from node ‘1’ to every nodes. Visited nodes and edges is presented by gray color.

step1. Initialize the node ‘1’ to ‘0’ and every nodes to infinite ( int(1e9 )

step2. Check the every edges which are connected with node ‘1’ and calculate the cost to move from node ‘1’ to other nodes.

step3. Choose the unvisited node ‘4’ which is shortest path in previous process. After then, check the every edges which are connected with node ‘4’ and calculate the cost to move from node ‘4’ to other nodes.

The nodes that node ‘4’ can move are node ‘3’ ,‘5’ and shortest path to node ‘4’ was 1. So the minimum cost to move ‘3’ is 4 ( 1 + 3 ) and to move ‘5’ is 2 ( 1 + 1 ).

These two values are lesser than previous values in the list so update node ‘3’, ‘5’ in the list .

step4. Choose shortest path node which is not marked a visit

2 is shortest path but there are two nodes of value 2 which is node ‘2’ and node ‘5’. In this case, choose the lesser number of node.

Check the every edges that are connected with node ‘2’ and calculate the cost to move form node ‘2’ to other nodes.

The node that node ‘2’ can move are node ‘3’ and ‘4’. The cost to move to ‘3’ is 5(2 + 3) and to move ‘4’ is 4 (2+2). These are greater than values in previous values in list so it isn’t updated.

step5. Choose shortest path node which is not marked a visit

choose node ‘5’ in this time.

Check the every edges that are connected with node ‘5’ and calculate the cost to move form node ‘5’ to other nodes.

The node that node ‘’ 5 can move are node ‘3’ and ‘6’. The cost to move to ‘3’ is 3(2+1) in this case 2 was 1 +1 in the previous node ‘5’ in list. Update node ‘3’ to 3. And the cost to move ‘6’ is 4(2+2) so update value of node ‘6’ to 4.

step 6. Choose shortest path node which is not marked a visit.

choose node ‘3’ in this time and repeat the previous processes.

step 7. Choose shortest path node which is not marked a visit.

choose node ‘6’ in this time and repeat the previous processes.

The list that is shortest path table means that shortest path is ( 2, 3, 1, 2, 4) from starting node ‘1’ to node ‘2’, ‘3’, ‘4’, ‘5’, ‘6’. So Dijkstra algorithm repeat the process ‘ Choose shortest path node which is not marked a visit ’.

3. Implement basic Dijkstra algorithm

Now, we are going to implement basic Dijkstra algorithm. This method is developed by Dijkstra and easy to understand. Firstly define 1-dimension list to store information of shortest distance about each nodes. After then, search every element in 1-dimension list in every steps to ‘ Choose shortest path node which is not marked a visit ’.

Following code use ‘sys.std.readline()’ method instead of ‘input()’ method because it readline() method is more faster than input() method. And every node assigned the index : ( number of node + 1 ) to directly access list. This is common method when using graph data structure so i recommend remember this technique.

import sys
input = sys.stdin.readline
INF = int(1e9)

# Input the number of nodes and edges
n, m = map(int, input().split())
# Input starting node
start = int(input())
# Create the list to store information about cennected nodes
graph = [ [] for i in range(n+1) ]
# Create the list to check visited nodes
visited = [False] * (n+1)
# Initialize shortest distance table to infinit
distance = [INF] * (n+1)

# Input every edge information
for _ in range(m):
   # 'c' is cost to move form 'a' to 'b'
   a,b,c = map(int, input().split() )
   graph[a].append((b,c))


def get_smallest_node():
    min_value = INF
    index = 0 
    for i in range(1, n+1):
        # Return shortest distance node which is not visited.
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # Initialize the starting node
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # Repeat n-1 nodes which is every node without starting node
    for i in range(n-1):
        # Mark a visit to shortest distance node
        now = get_smallest_node()
        visited[now] = True
      
        # Check current node and connected nodes
        for j in graph[now]:
            cost = distance[now] + j[1]
            # Update distance if the distance from current node to other node is shorter than previous distance
            if cost < distance[j[0]]:
                distance[j[0]] = cost

# start dijkstra
dijkstra(start)

# print shortest distance to every nodes
for i in range(1, n+1):
    # if it can't move, print infinity
    if distance[i] == INF:
        print("Infinity")
    # if it cna move, print distance
    else:
        print(distance[i])


"""

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2


0
2
3
1
2
4

"""

4. Implement advanced Dijkstra algorithm

Basic Dijkstra algorithm is can’t used when number of nodes are over 10,000. It searches the shortest table to find shortest distance node from first node to end node. In the advanced Dijkstra algorithm, it use ‘Heap data structure’.

Heap data structure is the data structure to implement Priority queue. Stack remove lastly input data and Queue remove firstly input data. Priority queue remove higher priority data. Higher priority data can be presented by integer variable. Python support the library ‘PriorityQueue’ and ‘heapq’. ‘heapq’ is more faster than ‘PriorityQueue’ so i recommend to use heapq method.

For example, there is information of stuff and it is consist of value of stuff and weight of stuff. Every data of stuff are combined as ( value , weight ) and are put to priority queue.

Python use Min heap to implement priority queue so the lower value of data are firstly deleted. If you want to use max heap, just add negative sign to priority data. Actually, list also make priority queue but it is slower than heap. Now, Let’s look at advanced Dijkstra algorithm. Please focus to how priority queue is changed step by step. Each nodes are listed in order from left side.

step 1. Starting node is ‘1’ and put the node to priority queue. At this time, Distance from node ‘1’ to node ‘1’ is ‘0’. So object information is ( distance : 0, node : 1 ) and put this object to priority queue.

‘heapq’ method in Python create priority queue by using this tuple type of information ( 0, 1 ). This tuple is sorted by order of distance.

step 2. Check the node in priority queue and mark a visit if it node is not visited yet because priority queue sort shortest distance.

Check the every edges which are connected with node ‘1’ and calculate the cost to move from node ‘1’ to other nodes.

The nodes that node ‘1’ can move are node ‘2’ ,‘3’, ‘4’. the minimum cost to move ‘2’ is 2( 0 + 2 ), to move ‘3’ is 5( 0 + 5 ) and to move ‘4’ is 1( 0 + 1 ).

Update the table and put these distance information to priority queue.

step 3. Node ‘4’ is first node in priority queue. Check the every edges which are connected with node ‘4’ and calculate the cost to move from node ‘4’ to other nodes.

The nodes that node ‘4’ can move are node ‘3’ ,‘5’ and shortest path to node ‘4’ was 1. So the minimum cost to move ‘3’ is 4 ( 1 + 3 ) and to move ‘5’ is 2 ( 1 + 1 ).

Update the table and put these distance information to priority queue.

step 4. Node ‘2’ is first node in priority queue. Check the every edges which are connected with node ‘2’ and calculate the cost to move from node ‘2’ to other nodes.

Get ConfidenceCoding’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The node that node ‘2’ can move are node ‘3’ and ‘4’. The cost to move to ‘3’ is 5(2 + 3) and to move ‘4’ is 4 (2+2).

These values are greater than values in table so pass to next step.

step 5. Node ‘5’ is first node in priority queue. Check the every edges which are connected with node ‘5’ and calculate the cost to move from node ‘5’ to other nodes.

The node that node ‘5’ can move are node ‘3’ and ‘6’. The cost to move to ‘3’ is 3(2 + 1) and to move ‘6’ is 4 (2+2).

Update the table and put these distance information to priority queue.

step 6. Node ‘3’ and Distance ‘ 3’ is first node in priority queue. The values in table are greater than other values so pass to next step.

step 7. Node ‘3’ and Distance ‘4’ is first node in priority queue. The values in table are greater than other values so pass to next step.

step 8. Node ‘6’ is first node in priority queue. Check the every edges which are connected with node ‘6’ and calculate the cost to move from node ‘6’ to other nodes.

The node ‘6’ is end of graph. The shortest distance cost is 4( 1 + 1 + 2 ).

Update the table and put distance information to priority queue.

step 9. Node ‘3’ is last element in priority queue but it is marked a visit. So terminate the process.

Let’s look at the code. Compared with previous code, this code don’t use ‘get_smallest_node()’.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
# Input starting node
start = int(input())
# Create the list to store information of each conntected node
graph = [ [] for i in range(n+1) ]
# Initialize distance table
distance = [INF] * ( n + 1 )

# Input every edge information
for _ in range(m):
    a, b, c = map(int, input().split())
    # 'c' is cost to move form 'a' to 'b'
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    # Input starting node and distance to priority queue
    heapq.heappush(q, (0, start))
    distance[start] = 0
    # terminate if priority queue is empty
    while q: 
        # Take the first elemenet in priority queue
        dist, now = heapq.heappop(q)
        # Pass current node is already visited
        if distance[now] < dist:
            continue
        # Check current node and connected edges
        for i in graph[now]:
            cost = dist + i[1]
            # Update if current distance is shorter than previous distance
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost, i[0]))

# Start dijkstra algorithm
dijkstra(start)

# Print shortest distances to every node
for i in range(1, n+1):
    # If it can't move, print infinity
    if distnace[i] == INF:
        pirnt("INFINITY")
    # If it can move, print distance
    else:
        print(distance[i])

"""

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2


0
2
3
1
2
4

"""

  

5. Floyd-Warshall algorithm

Dijkstra is the algorithm to find shortest distance from one node to other specific node. Floyd-Warshall is algoritm to find shortest distance from every node to every node. This algorithm doesn’t need to use the process to find the node that is shortest distance. It store information of shortest distance to 2-dimension node. Let’s look at formula of Floyd-Warshall algorithm

This formula means it will update if ‘ Distance from previous node ‘a’ to node ‘b’ ‘ is lesser than ‘ Distance from node ‘a’ to node ‘k’ + Distance from node ‘k’ to node ‘b’ ’ .

Following graph is detail example.

This graph can be changed to following table which is 2-dimension list.

The information of connected edges are put in table and the information of disconnected edges are put in table as “infinity”. Each values in table is distance from a to b. For example, Distance from node ‘1’ to node ‘4’ is 6 so the fourth column of the first row is 6. And Distance from node ‘1’ to node ‘1’ is 0 so every element on a diagonal line are 0.

step1. Check the case which pass node ‘1’. The formulas to find the answer is like these.

First formula means it will update if ‘ Distance from previous node ‘2’ to node ‘3’ ‘ is lesser than ‘ Distance from node ‘2’ to node ‘1’ + Distance from node ‘1’ to node ‘3’ ’ . It is same meaning if there is short distance when it pass node ‘1’, update distance to short distance. The spaces need to be change are gray collar in following table.

This table change after calculating 6 formulas.

step2. Repeat the same process to current table.

Check the cases which pass node ‘2’. The cases are ( 1, 3 ), ( 1, 4 ), ( 3, 1 ), ( 3, 4 ), ( 4, 1 ), ( 4, 3 ). Mark these cases to table as gray collar.

Algorithm will update these gray collar

step3. Repeat the same process to current table.

Check the cases which pass node ‘3’. The cases are ( 1, 2), ( 1, 4 ), ( 2, 1 ), ( 2, 4 ), ( 4, 1 ), ( 4, 2). Mark these cases to table as gray collar.

Algorithm will update these gray collar

step4. Repeat the same process to current table.

Check the cases which pass node ‘4’. The cases are ( 1, 2), ( 1, 3), ( 2, 1 ), ( 2, 3), ( 3, 1), ( 3, 2). Mark these cases to table as gray collar.

Algorithm will update these gray collar and result is like this

The number of node is 4 so final step is step 4. This table has every information of shortest distance from every nodes to every nodes. For example, the value in fourth column of first row is 6. this means the shortest distance from node ‘1’ to node ‘4’ is 6. Let’s make the code.

INF = int(1e9)

n = int(input())
m = int(input())
# Create the 2-dimension list and initialize every node to "Infinity"
graph = [ [INF] * ( n + 1 ) for _ in range( n + 1 ) ]

# Initialize distance from oneself to oneslef 
for a in range( 1, n + 1 ):
   for b in range( 1 , n + 1 ):
        if a == b:
            graph[a][b] = 0

# Initialize distance by using each distance.
for _ in range(m):
    # 'c' is distance from 'a' to 'b'
    a, b, c = map(int, input().split() )
    graph[a][b] = c

# Start Floyd-Warshall algorithm
for k in range(1, n + 1 ):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b] )

# Print the result 
for a in range(1, n + 1 ) :
    for b in range(1, n + 1 ):
        # If it can't move, print "Infinity"
        if graph[a][b] == INF:
            print("Infinity", end=" ")
        # If it can move, print distance
        else:
            print(graph[a][b], end=" ")
print()

"""
4
7

1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2


0 4 8 6 
3 0 7 9 
5 9 0 4 
7 11 2 0 
"""

Q1. Future city

Peter live in a city in the air and there are companies from 1st to Nth which are connected each others. Peter is current in 1st company and he want to sell the item after visiting companies N times. The road connect two companies and if it is connected, distance is 1. Peter move from current company to K th company and then he move from K th company to X th company. Make the program calculate shortest distance in this case.

For example, N = 5, X = 4, K = 5, The number of load is 7.

(1, 2), (1, 3), (1, 4), (2, 4), (3, 4), (3, 5), (4, 5)

Peter choose the route like this ( 1–3–5–4 ) and shortest distance is 3 in this case.

Solution

The key of solution for this problem is shortest distance form node ‘1’ to node ‘X’ and then move from node ‘X’ to node ‘K’ is ( distance node ‘1’ — node ‘X’ + distance node ‘X’ — node ‘K’). If you draw like following figure, you might know this is Floyd-Warshall algorithm problem.

The code is like this

INF = int(1e9)

# Input number of nodes and edges
n,m = map(int, input().split() )
graph = [ [INF] * (n+1) for _ in range(n+1) ]

# Initialize distance to 0 from oneself to oneself.
for a in range(1, n+1):
    for b in range(1, n+1):
        if a==b:
            graph[a][b] = 0

# Initialize distance to each edges
for _ in range(m):
    # Input distance as 1 from A to B
    a, b = map(int, input().split() )
    graph[a][b] = 1
    graph[b][a] = 1

# Input first destination X and final destination K
x, k = map(int, input().split())

# Start Floyd-Warshall algorithm
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# Print distance
distance = graph[1][k] + graph[k][x]

# Print -1 if it can't move
if distance >= INF:
    print("-1")
# Print distance if can move
else:
    print(distance)

"""

5 7
1 2

1 3
1 4
2 4
3 4
3 5
4 5 
4 5

3

"""

Q2. Send a telegram

There are N number of cities. If Peter send a telegram from city ‘X’ to city ‘Y’, the cable must be set between ‘X’ and ‘Y’ and ‘Y’ and ‘X’. It take time to send a telegram. Someday, There was an emergency in city ‘C’ so Peter want to send a telegram as possible as he can. The telegram will spread to start from current city ‘C’ to each cities by using cable. Make the program calculate the number of city and time when given information of city number and cable.

Solution

The range of N and M is wide so priority queue is fit for this problem. Furthermore, This question can be changed to shortest distance problem from one city to other city so we can use Dijkstra algorithm. We can make the program by using Dijkstra algorithm code we made.

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

# Input number of nodes, edges, starting node
n, m, start = map(int, input().split() )
# Make the list to store information of each node
graph = [ [] for i in range(n + 1) ]
# Initialize shortest distance table
distance = [INF] * (n+1)

# Input every edges
for _ in range(m):
    x, y, z = map(int, input().split() )
    # z is distance from x to y
    graph[x].append((y,z))

def dijkstra(start):
    q = []
    # Define shortest distance 0 to move starting node and put to queue
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        # take out information about shortest distance node
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        # Check the connected node with current node
        for i in graph[now]:
          cost = dist + i[1]
          if cost < distance[i[0]]:
            distance[i[0]] = cost
            heapq.heappush(q, (cost, i[0]) )

# Start dijkstra
dijkstra(start)

# The number of node can move
count = 0
# Shortest distance to furthest node in noe can move
max_distance = 0
for d in distance:
    # If it can move
    if d != INF:
        count += 1
        max_distance = max(max_distance, d)

# Print count - 1 to remove current node
print(count -1, max_distance)


"""
    
3 2 1
1 2 4
1 3 2

2 4

"""

Summary


1. Dijkstra algorithm : Calculate the distance to move from specific node to other node and update priority queue in the shortest path table

2. Floyd-Warshall : find shortest distance from every node to every node. It store information of shortest distance to 2-dimension node.