Professor Recitation

Dijkstra Algorithm

Dijkstra Algorithm: Algorithm used to find the shortest past between two distances.

What is different from the Minimum Spanning tree?

The shortest distance between two vertices might not include all the vertices of the graph.

Explanations

The reason is that the shortest distance between two nodes may not require visiting every node in the graph.

How Dijkstra Algorithm works
-Any subpath B->D of the shortest path A->D between vertices A and D is also the shortest path between vertices B and D.
Explanations
If you have found the shortest path between A and D, any subpath of that path between any two vertices is also the shortest path between those two vertices.
-Dijkstra used this property in the opposite direction. We overestimate the distance of each vertex from the starting vertex.
Then we visit each node and its neighbors to find the shortest subpath to those neighbors.
References

Why can’t Dijkstra Algorithm have a minus distance?
A: Because the algorithm doesn’t visit the vertex its visited.
Solution
BellmanFord Algorithm : |V|-1
갔던 곳 다시 감
Pigeonal Principle

But |V|-1 is => modify weight