Personally, I precalculate everything - there is no computational time involved unlike most other AI systems.
Depends on your level though and just how many nodes there are. However, even for something like a Half-Life game, I would use critical nodes.
In your above example - I can precalc the quickest route from 1 to 9 as 1,2,8,9.
Quickest path from 1 to 5 is 1,2,4,7,5
Each of your nodes has 1, 2, 3, or 4 routes. So, precalc'ing is going to be simple.
Depends on your level though and just how many nodes there are. However, even for something like a Half-Life game, I would use critical nodes.
In your above example - I can precalc the quickest route from 1 to 9 as 1,2,8,9.
Quickest path from 1 to 5 is 1,2,4,7,5
Each of your nodes has 1, 2, 3, or 4 routes. So, precalc'ing is going to be simple.