# What is the different between Dijsktra's algorithm and KNN?

I am implementing machine learning software and in my case, I am using K-nearest neighbour classifier to get the task done. So far, I am trying to understand how Dijkstra's algorithm that has been used to solve salesman travel problem is different from K-nearest neighbour algorithm?

• How are they similar ? The naive answer here would be everything. – MSalters Feb 24 '17 at 17:23
• what I mean that Dijsktra algo. is used to find the nearest neighbour as same as k-nearest neighbour algo. – Krebto Feb 24 '17 at 18:21
• They're totally unrelated. – D.W. Feb 24 '17 at 19:25

What is the different between Dijsktra's algorithm and KNN?

Almost everything.

$k$ nearest neighbor is a classification algorithm. It stores a list of [(features1, label1), (features2, label2), ..., (features-n, label-n)]. When it gets a new item features it calculates the distance to each of the $n$ stored items. It finds the $k$ closest ones. It returns the label which is most often in those $k$ examples.

Dijkstras algorithm is a graph search algorithm. It takes a graph $G = (V, E)$, a start node $s \in V$ and a target node $t \in V$ as input and returns the shortest path (v_1, \dots, v_n) with $v_1, \dots, v_n \in V$ from $s$ to $t$.

(You might be interested in the label correction algorithm, a generalization of Dijkstras algorithm)

## How they can be related. Somehow.

$k$ nearest neighbor can also operate on graphs. If you have a graph-like structure and your distance measure is e.g. the number of hops from a node, then you would use breadth first search.