Shorstest Path Problem Categories:

1. From a speicific start point;
2. To a specific end point;
3. Start and end with a specific point;
4. Search for all the shortest path in every pair nodes.

Dijkstra:

This algorithm is aiming at caculating all the shortest paths from every point to a specific start point. And it’s a greedy algorithm.

Algorithm:

1. Set the distance to the start node as infinity to all the nodes except the start node.
2. Initial a set which conclude the added nodes, and another set for unvisited nodes.
3. For the added nodes set, we find the shortest edge from adjancent nodes crossing this set in unvisited set. And add the adjancent node to the added added nodes.
4. Update the distances of nodes from start node which connect to the last added node.
5. Do step 3 and 4 repeatedly until all the nodes are in the added set.

Pseudoode:

function Dijkstra(Graph, source):

    create vertex set Q

    for each vertex v in Graph:             // Initialization
    dist[v] ← INFINITY                  // Unknown distance from source to v
    prev[v] ← UNDEFINED                 // Previous node in optimal path from source
    add v to Q                          // All nodes initially in Q (unvisited nodes)

    dist[source] ← 0                        // Distance from source to source

    while Q is not empty:
        u ← vertex in Q with min dist[u]    // Source node will be selected first
        remove u from Q 

        for each neighbor v of u:           // where v is still in Q.
            alt ← dist[u] + length(u, v)
            if alt < dist[v]:               // A shorter path to v has been found
                dist[v] ← alt 
                prev[v] ← u 

    return dist[], prev[]

Java Code:

public static void dijkstra(int[][] edges, int s, int[] dist, int[] pre) {
    int n = edges.length;

    HashSet<Integer> set = new HashSet<Integer>(n);

    for (int i = 0; i < n; i++) {
        dist[i] = Integer.MAX_VALUE;
        set.add(i);
    }
    dist[s] = 0;

    while (!set.isEmpty()) {
        int min = findMin(set, dist);
        for (int i = 0; i < n; i++) {
            if (edges[min][i] != -1) { // find the neighbors of the node
                if (dist[i] < dist[min] + edges[min][i]) { //relaxation
                    dist[i] = dist[min] + edges[min][i];
                    pre[i] = min;
                }
            }
        }
    }
}
private static int findMin(Set set, int[] dist) {
    int min = Integer.MAX_VALUE, minIdx = -1;
    for (int i = 0; i < dist.length; i++) {
        if (set.contains(i) && dist[i] < min) {
            min = dist[i];
            minIdx = i;
        }
    }
    set.remove(minIdx);
    return minIdx;
}

Running Time:

O(E*lgv)

If use the Fibonacci heap -> O(V*lgV + E)

Bellman Ford:

Aimming at searching for the shortest path from a specific start node. It is useful also for the graph containing the negative edges. It’s a dynamic programming algorithm.

Algorithm:

Question:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Thinking:

IIf the [i-1][j], [i][j-1] and [i-1][j-1] all have the same length of ‘1’ edge and the [i][j] is ‘1’, the length of the square can increase.

Solution:

public int maximalSquare(char[][] matrix) {
    int m = matrix.length;
    if (m == 0)    return 0;
    int n = matrix[0].length;
    int res = 0;
    int[][] opt = new int[m+1][n+1];

    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++) {
            if (matrix[i-1][j-1] == '1') {
                opt[i][j] = Math.min(opt[i-1][j-1], Math.min(opt[i-1][j], opt[i][j-1])) + 1;
                res = Math.max(res, opt[i][j]);
            }
        }
    }

    return res * res;
}

Question:

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Thinking:

We need three steps to finish this operation. The first one is to find the middle in the linked list. The second one is to reverse the second half of this linked list. The final one is to link these two parts again.

Solution:

public void reorderList(ListNode head) {
    if (head == null || head.next == null)    return;
    ListNode slow = head, fast = head.next, preMiddle, preCurrent, current, p, q;

    //find the middle
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    //reverse the second half
    preMiddle = slow;
    preCurrent = slow.next;
    while (preCurrent.next != null) {
        current = preCurrent.next;
        preCurrent.next = current.next;
        current.next = preMiddle.next;
        preMiddle.next = current;
    }

    //connect two parts
    p = head;
    q = preMiddle.next;
    while (p != preMiddle) {
        preMiddle.next = q.next;
        q.next = p.next;
        p.next = q;
        p = q.next;
        q = preMiddle.next;
    }

}

Reference:https://leetcode.com/discuss/35599/java-solution-with-3-steps

Question:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Thinking:

We can search the result from the start word. At every step, we change the every index of the start string and check if it’s in the WordList. If it’s in the range, then we add it to our nodes. Do it like a BFS search. Also in order to be more efficient, we can search also from the end word.

Solution:

public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    if (beginWord.equals(endWord))    return 1;
    Set<String> startSet = new HashSet<String>();
    Set<String> endSet =  new HashSet<String>();
    int res = 1;
    startSet.add(beginWord);
    endSet.add(endWord);
    while (!wordList.isEmpty() && !startSet.isEmpty() && !endSet.isEmpty()) {
        res++;
        Set<String> tempSet = new HashSet<String>();
        for (String nWord: startSet) {
            wordList.remove(nWord);
            for (String ele: check(nWord, wordList)) {
                if (endSet.contains(ele))    return res;
                tempSet.add(ele);
            }
        }
        startSet = tempSet;
        tempSet = new HashSet<String>();
        res++;
        for (String nWord: endSet) {
            wordList.remove(nWord);
            for (String ele: check(nWord, wordList)) {
                if (startSet.contains(ele))    return res;
                tempSet.add(ele);
            }
        }
        endSet = tempSet;
    }
    return 0;
}
private List<String> check(String word, Set<String> wordList) {
    List<String> res = new ArrayList<String>();
    int len = word.length();
    if (len == 1)    {
        res.addAll(wordList);
        return res;
    }
    for (int i = 0; i < len; i++) {
        char[] chs = word.toCharArray();
        for (char j = 'a'; j <= 'z'; j++) {
            chs[i] = j;
            String temp = String.valueOf(chs);
            if (wordList.contains(temp))    res.add(temp);              
        }
    }
    return res;
}

Question:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Thinking:

We should use dfs check the root of the range and both its left child and right child.

Solution:

public boolean isValidBST(TreeNode root) {
    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean helper(TreeNode root, long a, long b) {
    if (root == null)    return true;
    if (root.val <= a || root.val >= b)    return false;        
    return helper(root.left, a, root.val<b? root.val:b) && helper(root.right, root.val>a? root.val:a, b);
}