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

Using secrets in Azure Container Instances

Introduction


At work I am involved in one of our internal project development. This project is a relatively small (less than 30 pages) ASP.NET Core 3.1 Razor Pages application. From it’s first days application is hosted in Azure using Azure Container Instance, Azure SQL Database and Azure Key Vault (continues integration and deployment pipelines are powered by Azure DevOps).

There is nothing special in such setup, however as it happens with setups of this kind, there is one thing that has to be managed prior to implementing it – “How to securely pass secrets to Azure Container Instances and securely read secrets stored in Azure Key Vault (ex. read database connection string) from within Azure Container Instances?”

Finding the answer was my responsibility, so I have created a dummy project and dived into Azure documentation. This post contains results of my findings composed, as I hope, in easy and understandable format.

Continue reading “Using secrets in Azure Container Instances”

What is the difference between ToArray and ToList?

Introduction


In the beginning of June I attended .NET Summit conference in Minsk, Belarus. Besides interesting presentations (recording are available on YouTube, language is Russian / English) there were interesting quizzes.

One of the questions was:

What is the difference between ToArray and ToList?

Software Engineer

Hmm… what could be the difference besides one returns T[] and another one returns List<T>?

If you don’t know the answer or just like digging into sources of dotnet/corefx then I invite you to join me and find out the answer!

Note

All code snippets were taken from release/3.0 branch of dotnet/corefx repository. All code snippets were truncated to make them more representative (removed input argument checks, contracts, …, etc.).

Tests were targeting .NET Core 3.0 preview 7. However most of the information should be relevant for .NET Core 2.0+ and .NET Framework 4.5+.

Continue reading “What is the difference between ToArray and ToList?”

“html-escape” – a contributor’s story about Visual Studio Code extension

Have you ever find yourself typing ‘Escape html online‘ in Google search?

I’ve had 🙂

Recently I got tired of these searches and decided to look for an extension to Visual Studio Code, which I use for writing. This is where I met html-escape by Raymond Camden.

I used it for quite awhile a come up with some ideas of how to make it better. The problem was, these improvements required significant design changes. This has made me decide to start contributing.

In this post I invite you to join me in making these design changes. We will take a look at existing application feature set, get acquainted with some of Visual Studio Code concepts and theory, discuss application requirements, create application design (no architectural diagrams) and then literally implement all existing application features fitting them into our design.

Interested? Then let’s start.

Continue reading ““html-escape” – a contributor’s story about Visual Studio Code extension”