Cost table
- Algorithms course
- Advanced
- Lesson 18/56
- 4 min
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.
Practice 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()).
Starter code
def init_cities():
# Return city list
return ['A', 'B', 'C', 'D']
def init_cost():
# Return cost matrixSample 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())Expected output
[[0, 10, 25, 60], [0, 0, 20, 50], [0, 0, 0, 30], [0, 0, 0, 0]]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 DP recurrence
dp[i] = dp[j] + ____[j][i]dp[i] = dp[j] + cost[j][i]Explanation: cost is right.
2 Why is the diagonal zero?
- Wrong data
- No cost to same city Correct answer
- Infinite cost
- Negative cost
Explanation: There is no cost to go to the same city.
3 Cost table: match the terms
| Term | Meaning |
|---|---|
cost[0][1] |
A→B |
cost[1][2] |
B→C |
cost[2][3] |
C→D |
cost[0][3] |
A→D |