Metoda pe care ai prezentat-o nu are o eroare? De exemplu:
In matricea,
1 2 5
1 3 1
0 8 1
, algoritmul cand va ajunge in nodul (1,0), nu o sa aleaga intre 3 si 0 pe 0   , nodul (2,0) al matricei. In cazul in care va alege nodul (2,0) programul va afisa un rezultat eronat, deoarece drumul minim este : 1->1->3->1->1 si nu 1->1->0->8->1 !

Am reusit urmatoarea implementare :
Matrice :
10 3
1 2 5
1 3 1
0 8 1
10 = suma de bani avuta initial;
n = 3;
Programul afiseaza suma maxima de bani ramasa angajatului dupa ce traverseaza firma de la un birou la altul (1 - stanga sus; la 1-dreapta jos);

Cod:

/*Taxe*/
#include <stdio.h>
#define fin "taxe.in"
#define fout "taxe.out"

int n,s;
long int taxa[10][10];
long int taxaMin[10][10];
long int infinit=1000;

void citeste();
void drum();
int minTaxeVecini(int,int);
int minim(int,int);
void tipar();

void init(){
	for(int i=0;i<=n+1;++i)
	  for(int j=0;j<=n+1;++j)
	    taxaMin[i][j]=infinit;
	taxaMin[1][1]=taxa[1][1];
}

void main(){
	citeste();
	init();
        tipar();
	drum();
	tipar();
}

void citeste(){
	FILE *f=fopen(fin,"rt");
	fscanf(f,"%d %d\n",&s,&n);
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=n;++j)
	    fscanf(f,"%d",&taxa[i][j]);
        fclose(f);
}

void drum(){
	int i,j,min;
	int amOptimizare;

	amOptimizare=1;
	while(amOptimizare){
	  amOptimizare=0;
	  for(int i=1;i<=n;++i)
	    for(int j=1;j<=n;++j){
	      min=minTaxeVecini(i,j);
	      if(min+taxa[i][j]<taxaMin[i][j]){
		taxaMin[i][j]=min+taxa[i][j];
                amOptimizare=1;
	      }
	    }
	}
	if(taxaMin[n][n]<=s)
	  printf("%d\n",s-taxaMin[n][n]);
	else
	  printf("%d\n",-1);
}

int minTaxeVecini(int i, int j){
	int min1,min2;
	min1=minim(taxaMin[i-1][j],taxaMin[i+1][j]);
        min2=minim(taxaMin[i][j-1],taxaMin[i][j+1]);
        return minim(min1,min2);
}

int minim(int a, int b){
	if(a>b) return b;
	else return a;
}

void tipar(){
	for(int i=1;i<=n;++i){
	  for(int j=1;j<=n;++j)
	    printf("%d ",taxaMin[i][j]);
	  printf("\n");
	}
        printf("\n");
}

Folosesc HeapSort-ul si pana acum mi-a lasat impresia ca este cel mai rapid algoritm de sortare! Am lasat aici implementarea algoritmului :

Cod:

#include <stdio.h>
#include <conio.h>

void heapsort(int[],int);

void main(){
	clrscr();
	int i;
	int a[]={1,56,23,52,47,79,12,97};
	for(i=sizeof(a)/sizeof(*a);i>1;i--)
	  heapsort(a,i-1);
	for(i=0;i<sizeof(a)/sizeof(*a);i++)
	  printf("%4d",a[i]);
	getch();
}

void heapsort(int a[],int limita_a){
	int i,o;
	int fiu_stanga,fiu_dreapta,fiu_mijloc,radacina,temp;
	radacina=(limita_a-1)/2;
	for(o=radacina;o>=0;o--){
	  for(i=radacina;i>=0;i--){
	    fiu_stanga=2*i+1;
	    fiu_dreapta=2*i+2;
	    if((fiu_stanga<=limita_a)&&(fiu_dreapta<=limita_a)){
	      if(a[fiu_dreapta]>a[fiu_stanga])
		fiu_mijloc=fiu_dreapta;
	      else
                fiu_mijloc=fiu_stanga;
	    }else{
	      if(fiu_dreapta>limita_a)
		fiu_mijloc=fiu_stanga;
	      else
                fiu_mijloc=fiu_dreapta;
	    }
	    if(a[i]<a[fiu_mijloc]){
	      temp=a[i];
	      a[i]=a[fiu_mijloc];
              a[fiu_mijloc]=temp;
            }
          }
	}
	temp=a[0];
	a[0]=a[limita_a];
	a[limita_a]=temp;
	return;
}

Da, am reusit sa rezolv problema!
Va multumesc pentru ajutorul acordat, si pentru ca v-ati implicat!

Va multumesc pentru ajutor!
Intradevar, distanata minima este 1 -> 2 -> 3 -> 6 -> 9 ! Imi cer scuze pentru greseala facuta 

Buna ziua!
Doresc sa stiu cum pot determina lungimea minima dintre doua puncte ale unei matrice tinand cont ca nu te poti deplasa pe diagonala matricei (bidimensionala).
Ex matrice:
1 2 3
4 5 6
7 8 9
Distanta minima din coltul din stanga-sus pana in coltul din dreapta-jos este 21 : 1 -> 2 -> 3 ->6->9
Va multumesc !