A brief introduction of Dijkstra and shortest path with single sourse

Revision en1, by RDFZzzx, 2022-08-07 08:58:04

Problem statement

There is a kind of problems which want you to calculate the distant of the shortest path from some verdicts to other verdicts. This kind of problems are called "shortest path" in graph.

For example, in this graph, the distant of shortest path from verdict $$$1$$$ to verdict $$$6$$$ is $$$6$$$. And the distant of the shortest path from verdict $$$1$$$ to verdict $$$4$$$ is $$$5$$$.

Specifically, there are $$$2$$$ of subproblems in shortest path:

  • Single sourse (one start point)

  • Multi source (multi start point)

Dijkstra and shortest path with single sourse

In shortest path with single sourse, we should calculate the distant of the shortest path from one verdict (Lets suppose the sourse is verduct $$$1$$$) to others. Dijkstra is the most common algorithm to solve this sort of problems.

Node that Dijkstra can only solve the problems with nonnegtive edge weight. For graphs with negtive edge weight, you can only use Bellman Ford.

Dijkstra is a kind of greedy. In each turn, We select the verdict with the shortest distance from the sourse and get the shortest path to it. After that we update the distant from the sourse to other verdict.

Tags algorithms, graphs, shortest path, dijkstra

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English RDFZzzx 2022-08-07 13:31:22 2797 (published)
en1 English RDFZzzx 2022-08-07 08:58:04 1341 Initial revision (saved to drafts)