一个求最短总路径的问题

jihuyao

It is slow to learn new things when getting old.  I finally understand Dijkstra Algorithm after going over a detailed demonstration (like one shot to kill all birds).  So brute force backtracking approach for sudoku may do the same thing (as posted in new thread) for shortest path tree and probably for other related ones like traveler and shopping too.

But before forgetting following thought for current multiple traveler during Dijkstra algorithm learning process I would like to point out that sometimes even blind cat can catch dead rat.  So for 2 people why not shorten all possible sharable direct connections by half and then run Dijkstra algorithm to find a shortest path tree.  If lucky enough, one may find out both A and B are just on all the sharable paths (bingo!).  If not, it is still interesting to figure out why not and go further from there.

By the way, after understanding Dijkstra algorithm I am wondering if it can be implemented in sql (have not gone deep thinking on it).

jihuyao

Let me try again and see it gets through.  Basically, it does not have to be 50% for A and B on all sharable path.  One can set deferent ratios (from 0 to 100) on each sharable path.  Now it is really a partial random evolution approach like in even grouping problem.

newkid

jihuyao 发表于 2021-9-25 01:06
It is slow to learn new things when getting old.  I finally understand Dijkstra Algorithm after goin ...

我曾经见过有人写的用MODEL实现了Dijkstra算法。但是这个已经和传统SQL相差很远而且它的引用数组也不是真正的数组，效率差很多。SQL在算法实现中是没有优势的，只是某些情形下需要用到笛卡尔积时可能会少写一点代码。

jihuyao

Have not really think over the possibility but in the brute force backtracking code, each step can be completed in recursive sql and just not sure if deferent steps can be consolidated in one sql statement.  I can only say there is a chance here.

jihuyao

If can be implemented using model clause I would tend to believe it can be implemented in recursive sql.  Maybe it needs more than one thread, in odd step do one thing and in even step do another thing (2 steps represent 1 level only).