Winter Vacation Training Day 2 (01.27)

Area 2.2 : SPFA

Example :

Figure 4.1 : SPFA

SPFA(Shortest Path Faster Alogrithm)

is an algorithm sloving SSSP(single source shortst path) problem.

For the algorithm, we need an array and a queue.

For example, we need to find the distance between 1 and other points

Step 1 : push node 1 into queue, and set dist[1] = 0

Table 4.1-a : SPFA(a)

Next, pop the node 1, and relax all node v that (1, v) is in E.

If the node v is relaxed, push v into q.

Table 4.1-b : SPFA(b)

Repeat again :

Table 4.1-c : SPFA(c)

Node 4 has no edges to relax, so we only pop the element.

Table 4.1-d : SPFA(d)

Node 3 can relax (5, 2), so push node 2 into q.

Table 4.1-e : SPFA(e)

Node 2 has also no edges to relax, so we only pop the element.

Table 4.1-f : SPFA(f)

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

This is SPFA.

Given Score :
    Difficulty : 2
x   Basic Score : 49
Score : 264

[Area 2.3 Unlocked.]