Calculating the multiplicative inverse

Given a number x, find its multiplicative inverse y for a given modulo N
i.e. (x*y) == 1(MOD N)

Where the multiplicative inverse is useful?

Lets assume we need to compute ((a1 * a2 *....)/(b1 * b2 * .....)) mod N
1 simple way is to compute the above expression as

[Amazon Interview] Finding the shortest path

Given a matrix having non negative integers you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally)
e.g.
5 9 10 1
3 7 4 4
8 2 1 9
So shortest path from (0,0) to (2,2) - 5+3+2+1 = 11

Approach:

The matrix can be easily converted to a graph with each element having its neighbors as the up, down, left, right and diagonal elements.
Just pass this graph into any one of the Single source shortest path algorithm and you will find the minimum distance between the two elements 

Can we do better ?