1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.