Dijkstras | Routing Algorithms | Python Tutorial

Dijkstra's shortest path algorithm is a routing algorithm used in several fields such as network routing. Her were explain a popular example in simple terms and include the python code.
0:00 Dijkstra's algorithm
0:41 Dijkstra's algorithm uses
1:40 Dijkstra's routing example
6:03 Dijkstra's algorithm table
9:45 Dijkstra's algorithm in python
10:33 adjacency matrix
11:53 Dijkstra's algorithm vs UCS
www.drcodie.com/
[e-mail]
#pythontutorials
PYTHON PLAYLISTS ON CZcams:
Python Coder - Beginner
• Python Coder - Beginner
Python Fun & Games
• Python Fun Games
More Simple Python Tutorials
• simple python tutorials
Simple Python
• Simpe Python
Python Regular Expressions
• Python regular express...
WHY LEARN CODING WITH DR CODIE:
If you want to know how to learn python then these python programming tutorials are for you. Hi, my name is Dr Codie and I have helped many students to learn python, Scratch, SQL and other programming languages. In these videos you see how to learn python using your existing knowledge and gain some tips for learning python. Codie means ‘helpful person’ and we want to help you not just learn python programming but to enjoy learning python. We start with python tutorials for beginners and then move to tutorials for more advanced learning. The videos teach python 3.
In my experience, success being a python coder comes down to getting the fundamentals right. You can then move onto advanced programming concepts and skills. You will understand how to do simple coding tasks and then we will show you the simple methods of putting lines or blocks of code together using this knowledge. Practice is essential for your skills to grow but again do not fear we will help you practice as well.
Learn to understand the logic and design aspects needed to become a good programmer, let us help you practice to keep improving and don’t forget the bonus of seeing first hand how to build the code and possible stumbling blocks when we explain the answers to the tasks set within the tutorial. You do not need to watch the whole video but if you do you will improve as a python coder!
SOCIAL MEDIA
Pinterest: / codie0274
Twitter: / prepare15978094
Instagram: / drcodiecoder
Linkedin: / dr-codie-745021166
CZcams Channel: / @drcodie
SUBSCRIBE and you will know when the videos are available! Good luck!

[@DrCodie]

Due to continue with informed search algorithms with a* search, but we needed to cover the Dijkstra's algorithm first. We mentioned it several times but it is better to describe it clearly first. We will add other routing algorithms later but will go back to the informed algorithms with A* search next. That's the plan.

[@alexandrbihun7210]

UCS is optimal though

[@DrCodie]

It is always stated as optimal, but is it implemented as optimal, is it bidirectional? Online it is said to be optimal on conditions, for example, these are quotes: ''Yes, “optimal” shortest paths are found by best-first search algorithms as long as they use an admissible heuristics', and, 'The condition was that every step cost should be positive. It can never be zero or negative. Only then the algorithm is optimal.' So not zero or negative values and the heuristic can not overestimate. I hope this clarifies the optimal statement.

[@alexandrbihun7210]

​@@DrCodieUCS doesnt rely on a heuristic function thought. it chooses the next node to expand only in regards to the so called g-cost, which is the shortest distance found from start so far. It always chooses the node with the lowest g-cost, meaning it always finds the optimal path to every node, otherwise there would exist a better path and it would instead explore that path first.
Yes, UCS is an algorithm of the best first search class, because it chooses which node to expand according to some function f (f(n) = g(n) in this case), but it is not an informed algorithm, it doesnt have any addition information about the goal.
Obviously UCS doesnt work on graphs with negative weights, but the same also applies to Dijkstra's.
I think your implementation of UCS must be wrong, because it produces non-optimal results. I recommend looking into that. Also, in your comparisons of the two algorithms (in this video and in the video on UCS) you always implied that Dijkstra's is actually superior to UCS. Well you should reconsider that also, on large graph UCS works much better in practice, because it doesnt require the whole priority queue to be filled with nodes whose g-cost is infinity. Instead in only has to remeber the neighbors of already explored nodes.

[@DrCodie]

Interesting comments and I would be happy to make a new video to clarify the points you raise.
This is not the most effective implementation of UCS so it would be interesting to test the versions available to users. This is down to how the UCS algorithm is stopped, I quote ‘It depends on the stopping condition. If the stopping condition is "stop as soon as any vertex is encountered by both the forward and backward scan", then bidirectional uniform-cost search is not a correct algorithm -- it is not guaranteed to output the optimal path’[1].
‘UCS is a variant of Dijkstra’s Algorithm’ is the first sentence in the first result on a Google search (see [2]) and UCS is often taught as a simpler version because Dijkstra’s algorithm is ‘better-known’ [3]. Perhaps as Dijkstra’s Algorithm looks for the costs of all nodes it is considered superior, although, UCS has less space requirements.
Finally, UCS does not reply on a heuristic function - correct. As your comment was on the Dijkstra Algorithm video, when I mentioned the drawback of negative values I was thinking about this example of the Dijkstra’s Algorithm (see 14:00 czcams.com/video/XB4MIexjvY0/video.html ) not UCS.
I would say if I had not been clear or if it is in any way confusing or misleading then this should rectified. If you have a working knowledge of UCS then any important information that you feel should be highlighted please let me know. I would be happy to raise your matters, highlight any benefits of the UCS algorithm you suggest, compare online versions and make clear that the issues mentioned in previous videos are related to the implementation rather than the algorithm itself.
Thank you again for your comments.
Sources:
[1] www.geeksforgeeks.org/uniform-cost-search-dijkstra-for-large-graphs/
[2] ai.stackexchange.com/questions/24494/if-uniform-cost-search-is-used-for-bidirectional-search-is-it-guaranteed-the-so
[3] stackoverflow.com/questions/12806452/whats-the-difference-between-uniform-cost-search-and-dijkstras-algorithm