Similarities and differences between Java and C

As almost everybody knows Java was intended to be sort of C without pointers and to be used in smart home appliances. And then Gosling and his co-workers were drinking too much coffee and it come out more like C++ without pointers, resource management and multiple inheritance. So, how really different can be coding the same task in C and Java. Practically we are addressing just resource management part, we will not try to go OO in C. We implement fast Fibonacci algorithm in Java.

import java.math.BigInteger; public class Example { /* |1 1| <- we are using this row |1 0| */ static BigInteger[] Q = {BigInteger.ONE, BigInteger.ONE}; static BigInteger[] I = {BigInteger.ONE, BigInteger.ZERO}; /* F(2n+1) = F(n+1)^2+F(n)^2 F(2n) = F(n)*(2*F(n+1)−F(n)) */ static BigInteger[] squareIt(int n) { if (n == 0) return I; if (n == 1) return Q; BigInteger[] t = squareIt(n / 2); BigInteger[] res = {t[0].multiply(t[0]).add(t[1].multiply(t[1])), t[1].multiply(t[0].shiftLeft(1).subtract(t[1]))}; if(n%2==1) return new BigInteger[]{res[0].add(res[1]), res[0]}; return res; } public static void main(String[] env) { for(int i = 0; i<1000; i++) System.out.println("F("+i+") = "+squareIt(i)[1]); } }

It is really very fast, logarithmic fast. Now we try to do the same in C, we will skip BigInteger and use long. The first thing which wont work in C is array allocation, declaring them like that will create local variable. So we create function to allocate our arrays in order to return them to caller:

long * allocate(){ return (long*)malloc(2 * sizeof(long)); }

Those Q and I arrays can be global variables and we are ready to go, almost. We can not declare t as array since initializer can't be function call. Not big deal, we will use pointer to long but that introduces another problem. That pointer may point to global variables Q and I or allocated variables. Again we can check to what it points and if it doesn't point to Q or I we can call free. Already we have feeling that those arrays returned by squaring function are somehow polymorphic and in Java they were not like that. Allocating and freeing arrays on every step of recursion and checking should we free or not doesn't look right. Attempt to literally translate Java code may look something like this:

long * recurse(int i){ if(i==0) return I; if(i==1) return Q; long * t = recurse(i/2); long * r = allocate(); r[0] = t[0]*t[0]+t[1]*t[1]; r[1] = t[1]*((t[0]<<1)-t[1]); checknfree(t); if(i%2){ long * odd = allocate(); odd[0] = r[0]+r[1]; odd[1] = r[0]; free(r); return odd; } return r; }

If Q and I arrays are created using malloc we could do reassignments of initial array and free it at the end of calculation. So no global Q and I but they will be allocated on the heap and serve all recursive calls.

#include <stdio.h> #include <stdlib.h> long * allocate(int i){ long* res = (long*)malloc(2 * sizeof(long)); res[0] = 1; res[1] = i; return res; } long * recurse(int i){ if(i<2) return allocate(i); long * t = recurse(i/2); long t0 = t[0]*t[0]+t[1]*t[1]; t[1] = t[1]*((t[0]<<1)-t[1]); t[0] = t0; if(i%2){ t0 = t[0]+t[1]; t[1] = t[0]; t[0] = t0; } return t; } long square(int n){ long * result = recurse(n); long r = result[1]; free(result); return r; } int main(){ int i; for(i=0; i<93; i++) printf("F(%d) = %ld\n", i, square(i)); return 0; }

Now if we run valgrind on our program it will report:

==18896== HEAP SUMMARY:
==18896==     in use at exit: 0 bytes in 0 blocks
==18896==   total heap usage: 93 allocs, 93 frees, 1,488 bytes allocated
==18896== 
==18896== All heap blocks were freed -- no leaks are possible

Looking now at initial Java solution, it also could benefit from array reuse instead of allocating new ones on every step. Garbage collector is nice thing but not thinking at all about resource management may result in lower quality of code.

Functions, pointers, nested functions, clojures

While ago GCC introduced nested functions which are allowing easy solution of funargs problem. With funargs problem solved C can accommodate closures and provide everything what different modern languages can, except funny syntax. In order to demonstrate that we need function pointers and they are not part of modern languages derived from C. So, we start with function pointers refresher.

Function pointers

They are more cryptic than other pointers and they scare away younger generations of programmers. We will declare function and pointer to it:

int add( int i, int j) { return i + j; } int main(){ int (*fptr)(int,int) = add; printf("%d\n", fptr(2, 3)); return 0; }

We have return type, variable name in brackets and type list for parameters. We could also use address of operator during assignment. How we pass it as parameter?

int execute(int (*fptr)(int,int), int a, int b) { return fptr(a, b); } printf("%d\n", execute(fptr, 2, 3));

How we return it, write function which is returning function pointer? There is user friendly way, we declare typedef for function pointer:

typedef int (*fptra)(int,int); fptra get() { return add; } printf("%d\n", get()(2, 3));

But there is also user unfriendly way:

int (*fptr2fptr())(int, int) { return add; } int (*fptr)(int,int) = fptr2fptr(); printf("%d\n", fptr(2, 3)); printf("%d\n", (*fptr2fptr())(2, 2));

Return type of return type goes in front, inside first pair of brackets name and own parameters, inside the second pair of brackets list of parameter types of return type. And just for those who value extreme programming above all, pointer to function which returns function which returns function:

int (*(*f2f2f())(void))(int,int){ return fptr2fptr; } int (*(*f2f)())(int,int) = f2f2f(); int (*fadd)(int,int) = f2f(); printf("%d\n",fadd(4, 3));

Nested Functions

Those are GCC specifics and they are just ordinary functions but inside another function. Standard C will not let you define function within function. To demonstrate we can do trampolining of one notoriously recursive function.

int factorial(int i){ int acc = 1; void * f() { if (i < 2) return 0; acc *= i; --i; return f; } while(f()) continue; return acc; } int main() { int i; for(i = 2; i < 14; i++) printf("%d! is %d\n", i, factorial(i)); return 0; }

Here nested function is accessing variables which are host scoped and returns self or NULL. We got whole function back but we are not really using it, except to exit while loop if it is NULL. To remedy that we will dispatch those nested functions out of host function.

struct closure{ int counter; int visited; } data; int (*pgen(int i))(int){ int increase(int k){ data.counter += k; data.visited++; return data.counter; } int decrease(int k){ data.counter -= k; data.visited++; return data.counter; } if(i) return increase; return decrease; } int main(){ data.counter = 4; data.visited = 4; int (*incr)(int) = (*pgen)(1); int (*decr)(int) = (*pgen)(0); printf("counter = %d visited = %d\n", data.counter, data.visited); printf("counter = %d\n", incr(2)); printf("counter = %d\n", decr(1)); printf("counter = %d visited = %d\n", data.counter, data.visited); printf("counter = %d\n", incr(4)); printf("counter = %d\n", decr(1)); printf("counter = %d visited = %d\n", data.counter, data.visited); return 0; }

Here we have struct which is global variable, it is not really closure but just named like that, and one function generator. If we pass zero to generator we get one function back and for non zero the other one. Both nested functions now operating on global variable. In previous example we were working on variables belonging to host function, in this case if we try the same we will have problems since host's variables went out of scope.

Funarg problem

This one is related to functional languages and nested functions. If we pass nested function as argument to another function that is called downward funarg problem. Returning nested function to caller is upwards funarg problem. If any of passed or returned functions references variable from scope of declarer, those must be available to nested function so it can be executed. Passing nested function as argument to another function is not problem in C since all local variables of declarer are alive.

void execute(void(*fptr)(int), int i){ fptr(i); } void print(int(*fptr)(void)){ printf("counter = %d\n", fptr()); } int main(){ int counter = 0; void increase(int k){ counter += k; } void decrease(int k){ counter -= k; } int getter(){ return counter; } execute(increase, 3); print(getter); execute(decrease, 2); print(getter); return 0; }

Returning nested function is more problematic because declarer went out of scope. That could be addressed like in Java, if anonymous function uses some declarer's variable, that variable must be final. In C there is even more options, we can use static variables or allocate them on the heap.

int (*pgen(int i))(int){ static int counter = 0; int increase(int k){ counter += k; return counter; } int decrease(int k){ counter -= k; return counter; } if(i) return increase; return decrease; } int main(){ int (*incr)(int) = (*pgen)(1); int (*decr)(int) = (*pgen)(0); printf("counter = %d\n", incr(2)); printf("counter = %d\n", decr(1)); printf("counter = %d\n", incr(4)); printf("counter = %d\n", decr(1)); return 0; }

It is easier to use static than malloc and free. Removing static from counter declaration will result in exception during execution of program. So, funargs problem is not problem for C in GCC version. This makes C almost functional language, functional with few extras.

Recursive Squaring

This one neatly solves problem of log n multiplications to calculate nth power of of some number. It goes in two stages, calls self recursively with half power until it reaches power 0 or 1 and then squares results. If power was not even correction is required, additional multiplication with base.

static long pow(long base, int n){ if(n==0) return 1; if(n==1) return base; long acc = pow(base, n/2); acc *= acc; if(n%2 == 0) return acc; return base * acc; }

If we want to see how it works and how many times it calls self we can insert debug code:

static long powDbg(long base, int n, int depth){ for(int i = 0; i < depth; i++) System.out.print("-"); System.out.println(n); if(n==0) return 1; if(n==1) return base; long acc = powDbg(base, n/2,depth+1); acc *= acc; for(int i = 0; i < depth; i++) System.out.print("-"); System.out.println(n); if(n%2==0) return acc; return base * acc; }

Should have been included it in previous blog entries about recursion but better late than never.

Recursion and optimizations

As seen in last instalment calculating Fibonacci numbers using naïve implementation creates binary tree of calls and the same subtrees are calculated over and over again what has huge impact on performance. One of ways to improve performance is caching previous results and that is called memoization. In old Java we will do something like this:

private static final Map<Long, Long> memo = new HashMap<>(); static { memo.put(0L, 0L); memo.put(1L, 1L); } public static void main(String[] args) { System.out.println(fibonacci(0)); System.out.println(fibonacci(43)); System.out.println(fibonacci(92)); } static long fibonacci(long n) { if (memo.get(n) == null) { memo.put(n, fibonacci(n - 1) + fibonacci(n - 2)); } return memo.get(n); }

We initialize map container with result for first two cases, to avoid if statements, and later if there is mapping for input, we return it and if there is no mapping for input we calculate it. Without help from memoization naïve implementation will choke and die on input 92. Using Java 8 it becomes even shorter, here is just fibonacci method, everything else is the same:

public static long fibonacci(long n) { return memo.computeIfAbsent(n, m -> fibonacci(m - 1) + fibonacci(m - 2)); }

Signature of computeIfAbsent is the following:

default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

where n is key and function is interface Function, we defined it recursively and compiler was not upset. Memoization brings speed but takes space.
How do we turn tail call version into lambda. We can do this for example:

static Function<Long, Long> y = new Function<Long, Long>() { private long tailRecursive(long a, long b, long n) { if (n > 0) { return tailRecursive(b, a + b, n - 1); } return a; } public Long apply(Long x) { return tailRecursive(0, 1, x); } }; public static long fibonacciFunctional(long n) { return y.apply(n); }

what does not look very functional and very Java 8 because it is anonymous class. Another more Java 8 option is declaring functional interface with sufficient number of arguments:

interface FewArgs<T, U, V, R> { public R apply(T t, U u, V v); } static FewArgs<Long, Long, Long, Long> tailRecursive; static { tailRecursive = (a, b, n) -> { if (n > 0) return tailRecursive.apply(b, a + b, n - 1); return a; }; }

We also can not initialize it in one go, declare class field and initialize it, it must be done from some of host class methods.
Remaining optimization ideas are strictly related to Fibonacci numbers and not applicable to most other recursions. There is not so obvious way to generate Fibonacci numbers:

| 1 1 | n      | F(n+1) F(n)   |
| 1 0 |    =   | F(n)   F(n-1) |

If we rise matrix on the left, lets call it A, to power of n-1 its A[0][0] is Fn. We can prove it using induction. For n=1 our claim obviously holds, now

| F(n+1) F(n)   |   | 1 1 |
| F(n)   F(n-1) | x | 1 0 | =

|F(n+1)+F(n) F(n+1)+0|   |F(n+2) F(n+1)|
|F(n)+F(n−1) F(n)+0  | = |F(n+1) F(n)  |

Instead of doing chain multiplication we can do squaring and reduce number of multiplications to log(n) multiplications.

| F(n+1) F(n)   |2
| F(n)   F(n-1) | =

| F(n+1)^2+F(n)^2         F(n+1)*F(n)+F(n)*F(n−1)|
| F(n)*F(n+1)+F(n−1)*F(n) F(n)^2+F(n−1)^2        |

From where one can pull more interesting relations.
Here is illustrative implementation of this idea:

private static long square(long n) { if(n==0) return n; long test = n-1; ArrayList<long> arr = new ArrayList<>(); long[] A = new long[]{ 1, 1, 1, 0 }; long[] result = new long[4]; System.arraycopy(A, 0, result, 0, 4); while(test>1){ if(test%2!=0) arr.add(1L); else arr.add(0L); test/=2; } for(int i=arr.size()-1;i>-1;i--){ result=multiply(result,result); if(arr.get(i)==1) result=multiply(result,A); } return result[0]; } private static long[] multiply(long[] a, long[] b) { long[] result = new long[]{ a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3], a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3] }; return result; } public static void main(String[] arg) { for (int i = 0; i < 93; i++) { System.out.println("F(" + i + ") = " + square(i)); } }

That ArrayList is mapper, consumes some additional space but makes things easier to debug.

Recursion

Got recently homework to do as part of interview process, already described it here. After providing them with working solution, thoroughly tested, they decided not to speak with me. My conclusion is that was not so bad outcome.
While searching web for clues I discovered this Find all paths from source to destination.
Guy submits his code, peers do review, everything sounds nice.
I will refrain from reviewing particular solution but after looking at it I decided to write about recursion. My impression is that young generations of programmers are putting great effort into mastering frameworks and new features of programming languages but in the same time somehow missing basics. It also coincides with my exploration of new functional features of Java 8.
Recursion is when method, in Java, or function, in C, calls itself during execution. Execution of caller is suspended until callee finishes, then it proceeds. So, there must be some natural way for recursive calls to stop propagating themselves into infinity. If we are not traversing some kind of tree structure, or marking vertices as visited when traversing graph, we typically passing variable to control depth of recursion. Trivial example of recursion is calculation of factorial:

n! = n*(n-1)*(n-2)*...*2*1

It is defined for positive integers. Here is natural and naive implementation together with test:

public static void main(String[] args) { System.out.println("9! = "+factorial(9)); } static long factorial(long n){ if(n<0) return 0; if(n<2) return 1; return n*factorial(n-1); }

I could throw exception on negative n and assert is 9! equal to 362880. What stops recursion here from proceeding forever is that if statement in combination with decreasing n in recursive calls. Now in order to visualize how execution looks like we will add some debugging code.

public static void main(String[] args) { System.out.println("9! = " + factorial(9, 9)); } static long factorial(long n, long m) { for (int i = 0; i < m - n; i++) { System.out.print("-"); } System.out.println(n); if (n < 0) return 0; if (n < 2) return 1; long result = n * factorial(n - 1, m); for (int i = 0; i < m - n; i++) { System.out.print("-"); } System.out.println(n); return result; }

Code now prints current value of n and number of dashes is how deep we are into recursion. We can see how stack of frames is growing in debugger as well but this is nicer. Output of execution is:

9
-8
--7
---6
----5
-----4
------3
-------2
--------1
-------2
------3
-----4
----5
---6
--7
-8
9
9! = 362880

As expected it behaves in linear fashion. It can be much more interesting than linear, for that we will calculate Fibonacci numbers. In the case of Fibonacci numbers we have the following recursive definition:

Fn = Fn-1 + Fn-2

Trivial and naive implementation looks like this:

public static void main(String[] args) { System.out.println("F42 = " + fibonacci(42)); } static long fibonacci(long n) { if (n < 1) return 0; if (n < 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); }

Execution of this code will take  about second or two. Using 42 as function argument illustrates point that naïve implementation is not really most efficient. Mechanics of stopping recursive calls is identical to one in the case of factorial. Let us insert debugging code and see what is going on.

static int indent = 0; public static void main(String[] args) { System.out.println("F5 = " + fibonacci(5, 5)); } static long fibonacci(long n, long m) { for (int i = 0; i < m - n + indent; i++) { System.out.print("-"); } System.out.println(n); if (n < 1) return 0; if (n < 2) return 1; long result = fibonacci(n - 1, m); for (int i = 0; i < m - n + indent; i++) { System.out.print("-"); } System.out.println(n); indent--; result = result + fibonacci(n - 2, m); indent++; for (int i = 0; i < m - n + indent; i++) { System.out.print("-"); } System.out.println(n); return result; }

For reasonably sized argument of 2 we have this output:

2
-1
2
-0
2
F2 = 1

Argument 2 is decreased and recursive call is made with argument 1. When it returns to level 0 with result 1 next recursive call is made with argument 0. The second call also returns with result 0 to level 0 and we have 1+0=1 as result.
We try now 3 as argument:

3
-2
--1
-2
--0
-2
3
-1
3
F3 = 2

We start on level 0 with 3-1 call, then we have pattern from last run elevated for one level up, return to level 0 with result 1 and finally 3-2 recursive call and its return with result 1 to level 0. We can make conclusion that recursive calls are building binary tree. We can try argument 4 to recognize patterns for 3 and 2 and so on.
We could achieve the same on the factorial if we were splitting chain multiplication in half, I was writing about that here.
Recursive call does not have to return anything, work can be performed on one of function arguments. For example we can reverse array by swapping elements.

public static void main(String[] args) { String r = "Hello World!"; char[] arr = r.toCharArray(); reverse(arr, r.length()-1, 0); System.out.println(arr); } public static void reverse(char[] array, int hi, int lo) { if(lo>hi) return; char tmp = array[hi]; array[hi] = array[lo]; array[lo] = tmp; reverse(array, hi - 1, lo + 1); }

Here recursion stops when lo is bigger than hi.

Optimization

We can improve on naïve implementation using tail call elimination. We write method in such way that return statement is pure function call and that allows compiler to perform optimization and practically discard frames without placing them onto the stack. For example factorial can be rewritten like this:

static long tailRecursive(long acc, long n) { if (n == 0) return acc; return tailRecursive(n * acc, n - 1); }

We provide 1 as initial value for accumulator, n is the same as before. For Fibonacci we will need two accumulators:

static long tailRecursive(long a, long b, long n) { if (n > 0) return tailRecursive(b, a + b, n - 1); return a; }

Initial values are a = 0, b = 1 and n as before. From this form is quite easy to switch to iterative form.

static long notRecursive(long n) { if(n == 0) return 0; long a = 0; long b = 1; long c; do { c = b; b = a + b; a = c; --n; } while (n > 0); return a; }

About other forms of optimization like memoization, repeated squaring and lambdas, next time.

Scheduling and Johnson's Algorithm

There is actually paper available on the web where Johnson's scheduling algorithm is nicely described. You can find it here.
So that is not all-pairs shortest paths but scheduling one. For those who are lazy to read it, here is the story. We have programming task paired with testing task. We have one programmer and one tester, tester can test only what is coded, must wait for programmer to finish. In which order jobs should be executed so that whole bunch is finished in shortest time?
Now Johnson's algorithm in plain English:

1. For each task T1, T2, ..., Tn, determine the P1 and P2 times.
2. Establish two queues, Q1 at the beginning of the schedule and Q2 at the end of the schedule.
3. Examine all the P1 and P2 times, and determine the smallest.
4. If the smallest time is P1, then insert the corresponding task at the end of Q1. Otherwise, the smallest time is P2, and the corresponding task is inserted at the beginning of Q2. In case of a tie between a P1 and P2 time, use the P1 time.
5. Delete that task from further consideration.
6. Repeat steps 3 – 5 until all tasks have been assigned.

Very simple. Here is the code:

import java.util.ArrayDeque; import java.util.Deque; public class JavaApplication18 { public static void main(String[] args) { Tasks[] t = new Tasks[6]; for (int i = 0; i < 6; i++) { t[i] = new Tasks(); } t[0].programming = 15; t[0].testing = 4; t[1].programming = 22; t[1].testing = 10; t[2].programming = 3; t[2].testing = 6; t[3].programming = 12; t[3].testing = 8; t[4].programming = 9; t[4].testing = 6; t[5].programming = 12; t[5].testing = 9; executeAll(6, t); } static void executeAll(int n, Tasks[] t) { int[] order = getSchedule(n, t); System.out.println("order of execution is:"); for (int i = 0; i < n; i++) { System.out.println((char)(65+order[i]) + " " + t[order[i]].programming + " -> " + t[order[i]].testing); } System.out.println("Complete duration is " + calculateDuration(n, order, t)); } static int calculateDuration(int n, int[] order, Tasks[] t) { int max = 0, programmingTime = 0; int testingTime = 0, carry; for (int i = 0; i < n; i++) { programmingTime += t[order[i]].programming; carry = 0; if (testingTime > programmingTime) carry = testingTime - programmingTime; testingTime = programmingTime + t[order[i]].testing + carry; if (testingTime > max) max = testingTime; } return testingTime; } static int[] getSchedule(int n, Tasks[] t) { int[] order = new int[n]; int counter = 0, taskIndex = -1, min; Deque<integer> programmingDeque = new ArrayDeque<>(); Deque<integer> testingDeque = new ArrayDeque<>(); for (int j = 0; j < n; j++) { min = 2 ^ 16; kind task = null; for (int i = 0; i < n; i++) { if (!t[i].removed) { if (t[i].programming < min) { min = t[i].programming; task = kind.programming; taskIndex = i; } if (t[i].testing < min) { min = t[i].testing; task = kind.testing; taskIndex = i; } } } if (task == kind.programming) { programmingDeque.addLast(taskIndex); t[taskIndex].removed = true; } if (task == kind.testing) { testingDeque.addFirst(taskIndex); t[taskIndex].removed = true; } } while (programmingDeque.size() > 0) { order[counter++] = programmingDeque.removeFirst(); } while (testingDeque.size() > 0) { order[counter++] = testingDeque.removeFirst(); } return order; } enum kind { programming, testing }; static class Tasks { public int programming; public int testing; public boolean removed; } }

I think that code is self-explanatory and I will not bother you with explanation.
I also had a look at C++ code written by riteshkumargupta here it is slight modification of problem mentioned in paper. If you prefer C++ to Java take a look.

Find all paths from vertex to vertex in directed, weighted graph

Why I am doing homework? I have applied for a job at some company. They did some kind of phone interview and decided to give me “task” before they make up their mind will they ever talk to me about job again. OK, that evening I open Firefox and find in mailbox my tasks. That was few NP hard problems and I can pick and choose. Time for execution is limited, to make everything more interesting. Like reality show but you do not eat snails. Going quickly through them I realized that I am dealing with person who thinks that he or she is lecturer at university and that I do not have clue how to solve any of tasks.
BTW my educational background is physicist. Studied technical physics at school of electrical engineering at University of Belgrade. Never finished. As programmer I am self-educated. While I didn’t get university diploma I have learned to use literature.
Natural choice was the first task, it must be more important than others, that is the reason why it is the first. Task was something about finding all paths from vertex A to vertex B on weighted directed multigraph with cycles. Never encountered graphs before, only trees and they are part of the family. OK, time to google hard and yandex hard. After whole day of searching I got two clues. The first one is complete solution to generate all possible paths up to some length on Perl Monks and the other one is notes from some lecturing by Gunnar. Both clues claiming that adjacency matrix is a way to go and tool of choice is modified Floyd-Warshall. Learned quickly what I need and assembled working program based on degenerated matrix multiplication. After three days almost without sleep, submitted solution and went to bed. Next morning I figured out much simpler solution.
Now friendly warning, what follows is theory by somebody who studied graph theory for one whole day.

Adjacency matrix

Graph is one with directed edges, one way edges, multiple edges between pair of vertices may exist and there may be edge starting and finishing at the same vertex. Aadjacency matrix gives metric on graph space, who is neighbour to whom. Where you can go from some place.

     A    B    C    …    Z
A    1    0    0        1

From vertex A we can travel to A or Z in one move, to B and C we can't go in one move. Now comes curious tourist with question how far is B from A. If we start multiplying adjacency matrix with itself we will find out where we can go in two or more moves. Number of moves corresponds to power of adjacency matrix and if after rising it to power of 4 we see something like this:

     A    B    C    …    Z
A    0    2    1        4

meaning of it is we can't reach A in 4 moves, there is only one path to C but 2 paths to B and 4 paths to Z. Now to find out how many different paths exist from A to B where length of path is up to 4 moves one sums adjacencyMatrix[0][1] for powers from 1 to 4. Those are not shortest pats those are all possible paths including loops and cycles. Good reason to keep binary adjacency matrix around even if we got weights for edges.
So how do we go about finding those two or more moves paths, translating them in chain of edges? Since adjacency matrix is metric on that space we can use it to discover paths. For example where we can go from A in two moves.

     A    B    C    D
A    0    0    1    1
B    1    0    1    0
C    0    1    0    1
D    1    1    0    0

We can reach C or D in single move, from C we can get to B and D in single move and from D we can get to A and B in one move. So paths are ACB, ACD, ADA and ADB. That should be enough to write code for pathfinder.

Java implementation

From some vertex we can go where adjacency matrix says we can go and we move to next vertex. For that next vertex, we are in different row but we do the same thing. Looks like case for recursion. When frames start offloading from the stack they will bring us story where repeated recursive calls were taking them. We just need to send story back. If we do not limit depth of recursion it will never stop. BTW replace depth-1 with depth-- and --depth if you are not sure how suffix and prefix are different.

public ArrayList<string> findPath(int start, int end, int depth) { ArrayList<string> result = new ArrayList<>(); ArrayList<string> tmp = new ArrayList<>(); for (int i = 0; i < adjacencyMatrix.length; i++) { if (adjacencyMatrix[start][i] != 0) { if (i == end) { result.add(start + "," + end); } if(depth>1) tmp.addAll(findPath(i, end, depth-1)); } } if(tmp.size()>0) for (String s : tmp) { result.add(start + "," + s); } return result; }

We have built binary adjacencyMatrix and we are traversing graph. If we find target we store it but we proceed looking for target via calling all vertices which are reachable in single move. With limitation that depth of traversal is bigger than 1 and on each new call we are using reduced incoming depth. When function call comes back we append prefix to all paths. If you print content of that string array you will get something like:

2,3,2,3,2,3
2,3,2,4,1,2,3
2,3,4,1,2,3

It is the same format as used by blokhead from PerlMonks in his solution and you can nicely compare output of your code. Do not forget to make  adjacency matrix match :P
What about weights? Instead of having binary adjacency matrix we replace 1 with corresponding edge, actually weight of that edge. I will use integers for weights.

     A    B    C    D
A    0    0    3    5

Slightly modified traversal code:

public HashMap<String, Integer> findWeightedPath(int start, int end, int depth) { HashMap<String, Integer> result = new HashMap<>(); for (int i = 0; i < adjacencyMatrix.length; i++) { if (adjacencyMatrix[start][i] != 0) { if (i == end) { result.put(start + "," + end, adjacencyMatrix[start][i]); } if (depth > 1) { HashMap<String, Integer> tmp = findWeightedPath(i, end, depth - 1); if (tmp.size() > 0) { for (String s : tmp.keySet()) { result.put(start + "," + s, tmp.get(s) + adjacencyMatrix[start][i]); } } } } } return result; }

When you print content of that HashMap it looks like this:

2,3,2,3 = 23
2,3,4,1,2,3 = 33
2,3,2,4,1,2,3 = 35

It still stops on depth. If you need it to stop on weights sum then send data upstream. Don’t go for matrix multiplication if you do not have to, check other options. Nobody is going to ask you to find all paths between all vertices, to find all paths between two nodes recursive traversal looks much better than matrix multiplication.