Featured

Service Fabric Handbook

Welcome!

This post is a handbook where you probably will find an answer to “How different things works in Azure Service Fabric?” question. Almost all of the information (around 90%) is from docs.microsoft.com, GitHub and etc., the rest of it are personal findings made during development of CoherentSolutions.Extensions.ServiceFabric.Hosting.

Where possible the information will be confirmed by reliable source (docs, issues or posts).

Continue reading “Service Fabric Handbook”

.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#

Notice

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.

Introduction


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 (February, 2021)

Hello Everyone,

The first day of spring is here! So it is time for a new issue of .NET R&D Digest!

A fun fact is that I first started to publish this digest internally within the company and it’s internal number is #24, so it is been two years since the first digest issue ๐Ÿ˜Š

This issue contains bits of Life & Story, Architecture, .NET, .NET Internals, C# and tools.

Enjoy your reading!

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

.NET R&D Digest (December, 2020)

2020 is ending. It was a long and tough year for everyone. However, in world of software engineering it also was a quite interesting one – we saw how a plan become true (at least in .NET world, where Mono and .NET now share the same repo and .NET 5 was released as promised), we attended a lot of online events, online trainings and spent tons of time on self-education and we also read โ€ฆ .NET R&D Digest ๐Ÿ™‚

This issue contains bits of Visual Studio, .NET, web, databases, cloud, and software engineering.

Enjoy and see you next year!

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

.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)”