Cost table

Define a cost table between cities.

Cost matrix

The cost matrix cost[i][j] gives the cost of going from i to j. Since the graph is directed, cost[i][j] and cost[j][i] may differ; in our example only j > i has a value.

This structure is the basis of the dynamic programming solution. The matrix diagonal is zero because there is no cost to go from a city to itself.

Diagonal is zero

The matrix diagonal is always zero: cost[i][i] = 0. There is no cost to go from a city to itself.

This property keeps the cost table consistent and is the basis for the dynamic programming solution to work correctly.

Exercise init_cost function

Write init_cost(). Return the 4x4 cost matrix: diagonal 0, cost[0]=[0,10,25,60]. Print it with print(init_cost()).

Show example solution

def init_cities():
    # Return city list
    return ['A', 'B', 'C', 'D']
def init_cost():
    # Return cost matrix
    return [[0, 10, 25, 60], [0, 0, 20, 50], [0, 0, 0, 30], [0, 0, 0, 0]]
print(init_cost())

Test yourself

DP recurrence

dp[i] = dp[j] + ____[j][i]

Show answer

dp[i] = dp[j] + cost[j][i]

Why is the diagonal zero?
- Wrong data
- No cost to same city
- Infinite cost
- Negative cost
Show answer

No cost to same city — There is no cost to go to the same city.
Cost table: match the terms

cost[0][1]

A→B
cost[1][2]

B→C
cost[2][3]

C→D
cost[0][3]

A→D

Next lesson: DP solution

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies