Click here to Skip to main content
14,740,902 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
Posted
Updated 14-Nov-20 5:03am
Comments
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.


[update]
Fixed the wrong column index, thanks to Patrice T.
[/update]
   
v2
Comments
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