# C++ Self comment dj shortest path solution.

• ``````class Solution {
bool can_linked(string str_1, string str_2) {
if (str_1 == str_2) {return false;}
assert(str_1.size() == str_2.size() && !str_1.empty());
int pos = 0;
int check = 0;
for (; check < 2 && pos < str_1.size(); pos++) {
if (str_1[pos] == str_2[pos]) {

} else {
check++;
}
}
if (check == 1) {
return true;
} else {
return false;
}
}
struct x_node {
string val_;
int deepth_ = numeric_limits<int>::max();
vector<x_node*> neighbors_;
x_node(string v) : val_(v) {}
};
unordered_map<string, x_node*> map_;
set<x_node*> unvisited_;
set<x_node*> visited_;
int djs_from_to(x_node* b, x_node* e) {
unvisited_.emplace(b);
assert(b != nullptr);
b->deepth_ = 1;
while (!unvisited_.empty()) {
// pick smallest deepth in unvisited
x_node* to_visit;
int smallest_deepth = numeric_limits<int>::max();
auto found = for_each(unvisited_.begin(), unvisited_.end(), [&to_visit, &smallest_deepth](x_node* xn) {
if (xn->deepth_ < smallest_deepth) {
smallest_deepth = xn->deepth_;
to_visit = xn;
}
});
// visit it and update deepth of its neighbor
visited_.emplace(to_visit);
if (to_visit == e) {
}
unvisited_.erase(unvisited_.find(to_visit));
for (auto nei : to_visit->neighbors_) {
auto found_1 = visited_.find(nei);
if (found_1 != visited_.end()) {

} else {
unvisited_.emplace(nei);
if (nei->deepth_ > to_visit->deepth_ + 1) {
nei->deepth_ = to_visit->deepth_ + 1;
}
}
}
}
return 0;
}

public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
// build graph
for (auto s : wordList) {
x_node* nd = new x_node(s);
map_[s] = nd;
}
x_node* nd = new x_node(beginWord);
map_[beginWord] = nd;
// build neighbor of graph nodes
for (int i = 0; i < wordList.size(); i++) {
string s = wordList[i];
for (int j = i; j < wordList.size(); j++) {         // O(n2)
string ls = wordList[j];
map_[s]->neighbors_.push_back(map_[ls]);
map_[ls]->neighbors_.push_back(map_[s]);
}
}
}
for (int j = 0; j < wordList.size(); j++) {
string ls = wordList[j];