Winter Vacation Training Day 2 (01.27)

Area 2.3 : Dijkstra

Example :

Figure 5.1 : Dijkstra

Dijkstra is the same type as SPFA.

But it can’t solve the graph with an edge with minus weight.

For the algorithm, we need two arraies and a priority_queue.

Also, we need to find the distance between 1 and other point.

Step 1 : set the vis[1]=1, dist[1]=0 and push (0, 1) into pq.

Then, pop pq and get (dst, c) and relax node c.

Table 5.1-a : Dijkstra(a)

Next, we push all node v((1, v) is in E) that vis[v] is 0 (Here is 2).

So, we push (4.16, 2) into pq.

Table 5.1-b : Dijkstra(b)

Repeat Again :

Table 5.1-c : Dijkstra(c)

And again :

Table 5.1-d : Dijkstra(d)

Pop again, we got node 7.But it has no edges to relax.

So we pop over again and got node 5. Edge (5, 4) can relax.

Table 5.1-e : Dijkstra(e)

Then after pops, we got node 6 and 4.They both have no edges to relax.

Now, we got all the sp from 1 to any node again.

This is Dijkstra.

Given Score :
    Difficulty : 2
x   Basic Score : 81
Score : 426