Alice is a foreign student in Baku. She is planning to fly home to Madrid for a couple of weeks before her exams. While looking for tickets, she decided to practice for her Algorithms exam as well. Hence, she decided to create a weighted graph with the possible flights from Baku to Madrid, and vice versa. Below are all the flights she is considering and their ticket price in EUR:
Baku - Dubai (200)
Dubai - Madrid (300)
Baku - Istanbul (100)
Istanbul - Madrid (350)
Madrid - Baku (500)
Madrid - Istanbul (300)
Istanbul - Baku (150)
Dubai - Baku (200)Alice wants to apply some algorithms to this list to find the cheapest flight path, so she's decided to use an adjacency matrix to represent graph. What adjacency matrix will Alice end up with, considering that she uses the following order of cities in the matrix: Baku, Dubai, Istanbul, Madrid? The answer format should be the following:
0 100 200 300
200 0 inf 100
inf inf 0 300
90 inf inf 0
Tip: Consider the following points when constructing the adjacency matrix:
- Ensure that diagonal elements (same city to same city) have a weight of .
- Assign (infinity) to denote absence of direct flights between cities.
- Ensure each row of the matrix represents the source city, and each column represents the destination city.
- Remember to format the matrix with elements separated by spaces within rows and each row separated by a new line.