The Floyd-Warshall Algorithm

The classic Floyd-Warshall algorithm solves the "All-pairs shortest-path" problem on a weighted graph, namely, efficiently finding the length of the shortest route between every pair of vertices. It rests on the observation that if we denote the shortest path between A and B with {A,B}, then for every intermediate vertex K in {A,B}, {A,B}<={A,K}+{K,B}. A trivial recursive implementation follows:

floyd_warshall

    for each unordered pair (A,B)
        seen = [] // empty set
        min_paths[A,B] = fw_step(A,B)
        
fw_step A, B, seen

    if min_paths[A,B] exists
        return min_paths[A,B]
        
    min_path = |A,B| // direct distance between nodes
                     // may be infinity
                     
    seen[A,B] += 1 // dictionary keyed by unordered pair
    
    for each vertex K where seen[A,K] <= 1
                      and   seen[B,K] <= 1
        min_path = min(min_path, 
                       fw_step(A,K,seen) + fw_step(K,B,seen))
    
    return min_path

This is very inefficient. However, if we use an enumeration of all paths between A and B, based on the set of possible intermediate points [[], [0], [0,1], [0,1,2], ...], we can use that to remold the algorithm into an efficient dynamic programming solution:

    for K in [1; vertices] // for every vertex K find the shortest path {K,A,B}
    for A in [0; vertices) // that uses only [0..K-1] as intermediate nodes
    for B in [0; vertices)
        min_path[K, A, B] = min(min_path[K-1,A,B], 
                                min_path[K-1,A,K-1] + min_path[K-1,K-1,B])
                                
    // minimal paths for every A,B are in min_path[vertices, A, B]

A simple and neat O(n^3) solution to a daunting problem! Note that because we are checking the distance between nodes so often, the algorithm is vastly more efficient when using adjacency matrices rather than adjacency lists or edge lists for our graphs. Also, since in every iteration we're only using the previous enumeration level, min_path need only be of size 2*vertices^2:

    for K in [1; vertices]
    for A in [0; vertices)
    for B in [0; vertices)
        min_path[K%2, A, B] = min(min_path[(K-1)%2,A,B], 
                                  min_path[(K-1)%2,A,K-1] + min_path[(K-1)%2,K-1,B])
    
    // minimal paths for every A,B are in min_path[vertices%2, A, B]

Of course, this is overkill if you're only interested in the distance between two particular points - in that case, just use Dijkstra's algorithm, or some less general approach based on the specifics of your problem.

An important thing to note is that since the algorithm prefers shorter paths, it immediately ignores paths with cycles and repetitions (at least in the absence of negative edges); thus, it is not immediately adaptable to finding the longest paths by replacing min() with max(). It is possible to modify it for that purpose, however that requires looking out for malformed paths.

C# Riddles - Part I

A few tricky riddles and corner cases for wannabe C# language gurus:

// what gets printed / happens?
Console.WriteLine(null is object);

Console.WriteLine(null is IDisposable);

Console.WriteLine(null is int);

Console.WriteLine(null is int?);

Console.WriteLine(null is Func<int>);

Console.WriteLine(null is FileMode);

Console.WriteLine(0 is FileMode);

Console.WriteLine(0 is int?);

Console.WriteLine((((short)10)/((short)5)).GetType());

Console.WriteLine(new Nullable() is bool);

Console.WriteLine(new Nullable(false) is bool);

Console.WriteLine(new Nullable(false) is Nullable);

Console.WriteLine(new Nullable() is Nullable);

Console.WriteLine(null  + (int?)100 + "");

Console.WriteLine(null  + ""  + (int?)100);

Console.WriteLine(20 + 45 + "A");

Console.WriteLine("A" + 20 + 45);

Console.WriteLine(-int.MinValue);

string x = new string(new char[0]);
string y = new string(new char[0]);
Console.WriteLine(object.ReferenceEquals(x, y));

Console.WriteLine(default(int?));

Console.WriteLine(default(int?).GetHashCode());

Console.WriteLine(default(int?).GetType());

var ii = 1;
Console.WriteLine(ii += ii += ii += ii);

var ii = 0;
Console.WriteLine(ii = ii++);

Foo(this object obj) { return DateTime.Now.Seconds; }
...
Console.WriteLine(null.Foo());

int Rec(int i) { return (i < int.MaxValue) ? Rec(i + 1) : i; }
...
Console.WriteLine(Rec(0));

var array = new string[] { "foo", "bar", "cons" };
var objs = (object[])array;
objs[0] = 1000;
Console.WriteLine(objs[0]);

enum Foo { Bar, Baz }
...
Foo f = 0.0;
Console.WriteLine(f);

void Foo(object x) { Console.WriteLine("object"); }
void Foo(params T[] x) { Console.WriteLine("params T[]"); }
...
Foo("Hello");

struct Test
{
    static Test instance;
    static public Test Instance { get { return instance; } }
    
    public int field;
}
...
Test.Instance.field = 1;
Console.WriteLine(Text.Instance.field);

for(int ii = 0; ii < 10; ++ii)
  Console.WriteLine(new Random().Next(0, Int32.MaxValue));

var nums = new List<Func<int>>();
for (int ii=0; ii < 10; ii++)
    nums.Add(() => ii);
foreach (var num in nums)
    Console.WriteLine(num());

var nums = new List<Func<int>>();
foreach(var ii in Enumerable.Range(0,10))
    nums.Add(() => ii);
foreach (var num in nums)
    Console.WriteLine(num());

abstract class Base
{
    public virtual void foo(string s = "base") { Console.WriteLine("base " + s); }
}

class Derived : Base
{
    public override void foo(string s = "derived") { Console.WriteLine("derived " + s); }
}
...
Base b = new Derived();
b.foo();

throw null;

Exception GetException() { return new Exception(); }
...
throw GetException();

throw ((() => new Exception())());

throw ((() => { throw new Exception();} )());

// can your computer do arithmetic?

Console.WriteLine(1.0 + 1.0 == 2.0);

Console.WriteLine(0.01 + 0.01 == 0.02);

Console.WriteLine(0.00000037 + 0.0000001 == 0.00000047);

Console.WriteLine(0.9999999+0.000001 == 1.0);

Console.WriteLine(1.000001-0.000001 ==1.0);

/* assume InvariantCulture */
Console.WriteLine(4.170404 == Convert.ToDouble("4.170404"));

Console.WriteLine(Convert.ToInt32(13.6) == (int)13.6);

// does this compile?

const string foo = "aaa" + "bbb";
const string bar = "aaa" + 123;
const string frob = null;
const string squawk = (string)'\0';

// riddles
When can execution leave a try { } finally { } without executing the finally code?
How can you lock across AppDomains?
How can a string.Compare() call cause an AssemblyLoadException?
How can you create an instance of System.Void?

Sources:
- my own experience
- http://dotnetgeek.tumblr.com/post/11303229042/c-nullable-gotcha
- http://stackoverflow.com/questions/194484/whats-the-strangest-corner-case-youve-seen-in-c-sharp-or-net
- http://www.yoda.arachsys.com/csharp/teasers.html
- http://ahuwanya.net/blog/post/C-Brainteasers-Part-I.aspx
- http://stackoverflow.com/questions/241134/what-is-the-worst-gotcha-in-c-sharp-or-net