[FIXED] How do I store information for weighed graph without running out of memory?

Issue

So I've got a task with cities and roads. Each road between cities has it's price. There are lots of cities and some of them are connected with roads having different prices. How do I store that information? Information is read from file and then put into a Two-dimensional array. numbers{0} and numbers{1} contain the numbers of two connected cities while numbers{2} is the price of the road. So indexes of this array are the numbers of the cities and the number under those indexes is the price.

int[,] graph = new int[cities, cities];
for (int i = 0; i < roads; i++)
        {
            numbers = ReadFromFile(input);
            graph[numbers[0] - 1, numbers[1] - 1] = numbers[2];
            graph[numbers[1] - 1, numbers[0] - 1] = numbers[2];
        }

It works, but a big part from the tests it has to pass are failed. And the reason is that at some point it has to store 5000 * 5000 values for 5000 cities and it runs out of memory. What cain I do to avoid this? I thought about other options but nothing comes to mind that is better than this one. A snapshot

Solution

Before doing anything else try converting the project to work in x64 architecture instead of "Any CPU" or "Win32". This could make some memory problems simply go away.

Ideally you should use "sparse arrays" or "sparse matrices". There are some projects on the net, but they could be unwieldy. Next best thing is to simulate a sparse array using a dictionary and two single dimensional arrays instead of the big matrix.

The dictionary has Tuple<int, int> as key (two ints are coordinates of a cell) and road prices as value (if only one road can connect two cities then value is an int, for multiple roads between two cities it's List<int>).

Two single dimensional arrays are used to find non-empty cells in the dictionary. One array for each coordinate, so both with size 5000, they contain a List<int> list of all coordinates in another axis where there are non-empty cells. Depending on your search algorithm you might need only one such array, for x-axis for example (and the other for y-axis is not needed).

Answered By - Dialecticus

Answer Checked By - Timothy Miller (PHPFixing Admin)