Sort a K-Sorted Array

Given a k-sorted array that is almost sorted such that each of the N elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.

Single-Source Shortest Paths – Dijkstra’s Algorithm

Given a source vertex s from set of vertices V in a weighted graph where all its edge weights w(u, v) are non-negative, find the shortest-path weights d(s, v) from given source s for all vertices v present in the graph.