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.