.NET R&D Digest (April, 2021)

Today is the last day of April which is also turned out to be a Friday, and, what is always nice to have before weekend? – something to read! ๐Ÿ˜Š So, here is a new issue of .NET R&D Digest, just for that!

This issue contains bits of computer science, operating systems, security, performance, diagnostics, CSS, .NET and interesting tools to explore.

Enjoy and have a great weekend!

Continue reading “.NET R&D Digest (April, 2021)”

Implementing Floyd-Warshall algorithm for solving all-pairs shortest paths problem in C#


This post is a free form translation (with some clarifications) of my post in Russian published on techrocks.ru. So if you know Russian, you are welcome to read it there. Otherwise, I invite you to join me here and have some fun.


All of us solve a “shortest path” problem many times a day. Unintentionally of course. We solve it on our way work or when we browse the Internet or when we arrange our things on a desk.

Sounds a bit… too much? Let’s find out.

Imagine, you have decided to meet with friends, well … let’s say in cafe. First of all, you need to find a route (or path) to cafe, so you start looking for available public transport (if you are on foot) or routes and streets (if you are driving). You are looking for a route from your current location to cafe but not “any” route – the shortest or fastest one.

Here is a one more example, which isn’t so obvious as the previous one. During you way work you decide to take a “short cut” through a side street because well… it is a “short cut” and it is “faster” to go this way. But how did you know this “short cut” is faster? Based on personal experience you solved a “shortest path” problem and selected a route, which goes through the side street.

In both examples, the “shortest” route is determined in either distance or time required to get from one place to another. Traveling examples are very natural applications of graph theory and “shortest path” problem in particular. However, what about the example with arranging things on a desk? In this case the “shortest” can represent a number or complexity of actions you have to perform to get, for example, a sheet of paper: open desk, open folder, take a sheet of paper vs take a sheet of paper right from desk.

All of the above examples represent a problem of finding a shortest path between two vertexes in a graph (a route or path between two places, a number of actions or complexity of getting a sheet of paper from one place or another). This class of shortest path problems is called SSSP (Single Source Shortest Path) and the base algorithm for solving these problems is Dijkstra’s algorithm, which has a O(n2) computational complexity.

But, sometimes we need to find all shortest paths between all vertexes. Consider the following example: you are creating a map for you regular movements between home, work and theatre. In this scenario you will end up with 6 routes: work -> home, home -> work, work -> theatre, theatre -> work, home -> theatre and theatre -> home (the reverse routes can be different because of one-way roads for example).

Adding more place to the map will result in a significant grow of combinations – according to permutations of n formula of combinatorics it can be calculated as:

A(k, n) = n! / (n - m)!

// where n - is a number of elements, 
//       k - is a number of elements in permutation (in our case k = 2)

Which gives us 12 routes for 4 places and 90 routes for 10 places (which is impressive). Note… this is without considering intermediate points between places i.e., to get from home to work you have to cross 4 streets, walk along the river and cross the bridge. If we imagine, some routes can have common intermediate points… well … as the result we will have a very large graph, with a lot of vertexes, where each vertex will represent either a place or a significant intermediate point. The class of problems, where we need to find all shortest paths between all pairs of vertexes in the graph, is called APSP (All Pairs Shortest Paths) and the base algorithm for solving these problems is Floyd-Warshall algorithm, which has O(n3) computational complexity.

And this is the algorithm we will implement today ๐Ÿ™‚

Continue reading “Implementing Floyd-Warshall algorithm for solving all-pairs shortest paths problem in C#”

.NET R&D Digest (August, 2020)

The summer is over! ๐Ÿ˜ฆ But as Monday starts a new week (at least here in Belarus), September starts a Fall, where according to schedules, we can expect many new releases and events, so stay tuned!

This issue (August 2020) might seem smaller than usual but this isnโ€™t entirely true โ€ฆ because 40% of it are pair posts or series! Which gives us not 10 but 21 positions in overall ๐Ÿ˜Š

This issue includes bits of .NET, quantum computing, computer science, Visual Studio and PowerShell.

Have a great read!

Continue reading “.NET R&D Digest (August, 2020)”

.NET R&D Digest (May, 2020)

Today is the last Friday of the last Spring month โ€“ the last Friday in May. But do not hurry to say goodbye to the Spring โ€“ you still have a weekend to celebrate it, and, as you know, the best (or at least not the worst) way to spend your weekend is reading or watching interesting and exciting technical articles and videos, which, by the way, you can find in a new issues of .NET R&D Digest!

This issue includes bits of computer science, software development, .NET and more.

Enjoy and have a great weekend!

P.S. Don’t be tricked by the issue size, there is more than meet the eye (c).

Continue reading “.NET R&D Digest (May, 2020)”