Click here to Skip to main content
15,668,517 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I was given a sample file. Each row contains: two nodes, and a cost
I want to create a list where I have an adjacency matrix representation, from which I can implement Dijkstra's shortest path Algorithm.
For example, suppose I was given this sample graph:

0 3 .92
0 6 .97
1 2 .94
1 3 .91
1 4 .93
2 3 .95
2 4 .98
2 5 .92
3 5 .91
4 5 .94
4 6 .99
5 6 .92

How would I go about changing the contents of the file into adjacency matrix representation.

I would have hardcoded this, but I want a scenario where I do not know the contents of a file and I want to have adjacency matrix representation of the file which can contain up to 20 nodes.

I hope that makes sense.
Any help would be really appreciated. Thank you

What I have tried:

I just need an idea on how to do this
Updated 14-Nov-20 4:03am
Richard MacCutchan 14-Nov-20 4:52am    
That is a mathematics question. Once you understand the maths then the Python code should be fairly easy.

1 solution

I would do that this way:
  • Scan the file in order to find the minimum and maximum row and column indices. For simplicity sake, let's say the minima are zeroes and maxima are max_row and max_col.
  • Create a bidimensional list having (max_row + 1) rows and (max_col + 1) columns. Initialise all the items of the bidimensional list with 0.
  • Scan the file again, assigning the proper value to the corresponding item of the bidimensional list (e.g. 0 3 .92 => m[0][3] = .92.

That's all, folks.

Fixed the wrong column index, thanks to Patrice T.
Share this answer
Patrice T 14-Nov-20 10:17am    
Are you sure ?
0 3 .92 => m[0][2] = .92
  ^             ^
Richard MacCutchan 14-Nov-20 11:08am    
You have heard of Polish notation; this is the Italian version, which is far more relaxed. :)
CPallini 14-Nov-20 17:07pm    
Indeed. :-D
Patrice T 14-Nov-20 18:18pm    
Personally, I prefer Reverse Polish Notation (RPN)?
Because I learned to use calculators with dad's HP67. :)
CPallini 14-Nov-20 17:07pm    
Indeed, it is the relaxed Italian notation.
Thank you for pointing it out.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900