Sometimes, people find the names of algorithms familiar: for example, when it comes to finding a shortest path using Dijkstra's or sorting of data using Quicksort. There, however, exist hundreds of other very less-known algorithms that are equally strong and have massive impacts. Some of them do specific jobs well and might therefore be applicable in very-niche use cases.

We'll examine a few such algorithms, their applications, and then provide you with simple coding examples to get you started.

1. Floyd-Warshall Algorithm

Use Case: Finding shortest paths between all pairs of nodes in a weighted graph.

The Floyd-Warshall algorithm is used for dense graphs where you want to find the shortest path between every pair of vertices. It can work even with negative edge weights, given there are no negative weight cycles.

How It Works:

  • Uses dynamic programming.
  • Updates the shortest paths by considering each vertex as an intermediate point.

Python Code

python
def floyd_warshall(graph):
    n = len(graph)

dist = [[float('inf')] * n for _ in range(n)]

# Initialize distances based on input graph
for i in range(n):
    for j in range(n):
        if i == j:

dist[i][j] = 0
elif graph[i][j]:
dist[i][j]=graph[i][j]

    ### Dynamic programming to find shortest paths

for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

return dist

Example graph represented as an adjacency matrix

graph = [
[0, 3, float('inf'), 5],
[2, 0, float('inf'), 4],
[float('inf'), 1, 0, float('inf')],
[float('inf'), float('inf'), 2, 0]
]
shortestpaths = floydwarshall(graph)
print(shortest_paths)

2. Knuth-Morris-Pratt (KMP) Algorithm Patterns finding in strings.

KMP is an efficient algorithm for finding a substring in a given text. It differs from the naive string matching algorithm since it preprocesses the pattern to avoid useless comparisons.

How It Works:

  • Calculates a partial match table (LPS array).
  • Uses the table to avoid redundant comparisons.

Python Code:

python
def kmp_search(text, pattern):
    def compute_lps(pattern):
        lps = [0] * len(pattern)

length, i = 0, 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
lps[i] = length
                i += 1
            else:
                if length != 0:
length = lps[length - 1]
                else:
                    lps[i] = 0
i += 1
        return lps

    lps = compute_lps(pattern)
    i, j = 0, 0
    while i < len(text):
        if pattern[j] == text[i]:
i += 1
            j += 1
        if j == len(pattern):
            return f"Pattern found at index {i - j}"
elif i < len(text) and pattern[j]!= text[i]:
            j = lps[j - 1] if j!= 0 else 0
    return "Pattern not found"

text = "ababcabcabababd"
pattern = "ababd"
print(kmp_search(text, pattern))

3. Aho-Corasick Algorithm.

This algorithm is ideal to search for multiple patterns in a single text efficiently. It is used in almost all search engines and spam detection systems.

How it Works:

  • It constructs a trie of patterns.
  • It uses a failure function to skip unnecessary checks.

Python Code:

python
from collections import deque, defaultdict

class AhoCorasick:
    def __init__(self):
        self.trie = defaultdict(dict)
self.output = defaultdict(list)
        self.fail = {}

     def build_trie(self, patterns):
        for idx, pattern in enumerate(patterns):
            current_node = 0
for char in pattern:
            if char not in self.trie[current_node]:
                self.trie[current_node][char] = len(self.trie)
current_node = self.trie[current_node][char]
            self.output[current_node].append(idx)

    def build_failure_links(self):
        queue = deque()
        for char, node in self.trie[0].items():
self.fail[node] = 0
            queue.append(node)

        while queue:
            current = queue.popleft()
for char, next_node in self.trie[current].items():
                fail = self.fail[current]
                while fail and char not in self.trie[fail]:
fail = self.fail[fail]
                self.fail[next_node] = self.trie[fail].get(char, 0)
                self.output[next_node] += self.output[self.fail[next_node]]
queue.append(next_node)

    def search(self, text):
        node = 0
        for i, char in enumerate(text):
            while node and char not in self.trie[node]:
node = self.fail[node]
            node = self.trie[node].get(char, 0)
            if self.output[node]:
                print(f"Pattern found at index {i}")

patterns = ["he", "she", "his", "hers"]
ac = AhoCorasick()
ac.build_trie(patterns)
ac.build_failure_links()
ac.search("ahishers")

Conclusion

These lesser-known algorithms showcase the diversity and depth of computational problem-solving techniques. While they may not always be the first choice, they are indispensable in specific scenarios. By understanding and applying them, you can solve problems more efficiently and expand your algorithmic toolkit.

Try Them Yourself:

Explore these algorithms and try playing around with the code. They really can be game-changers in optimizing your solutions for real-world challenges!

Comments(0)