[算法] dijkstra单源无负权最小路径算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 1000000
#define MAXN 32

int N;
int matrix[MAXN][MAXN];

int dist[MAXN];
int path[MAXN];
int s[MAXN];

void dijkstra(int u){
   
/* init */
   
int i, j, k;
   
int min;
   
int v;
   
int tmp;

   
for(i =0; i < N; i++){
        s
[i]=0;    
        dist
[i]= matrix[u][i];
       
if(dist[i]!= INF && i != u){
            path
[i]= u;
       
}
       
else{
            path
[i]=-1;
       
}
   
}
    s
[u]=1;
    dist
[u]=0;
   
   
for(i =1; i < N; i++){
        min
= INF;
       
for(j =0; j < N; j++){
           
if(!s[j]&& dist[j]< min){
                min
= dist[j];    
                v
= j;
           
}
       
}    
        s
[v]=1;
       
for(k =0; k < N; k++){
           
if(s[k]){
               
continue;    
           
}
            tmp
= dist[v]+ matrix[v][k];
           
if(dist[k]> tmp){
                dist
[k]= tmp;
                path
[k]= v;
           
}            
       
}
   
}
}

void print_path(int u){
   
int rev[MAXN];
   
int count =0;
   
int i;
   
int v;
   
    memset
(rev,0,sizeof(rev));

    rev
[count++]= u;
    v
= path[u];
   
   
while(v !=-1){
        rev
[count ++]= v;
        v
= path[v];    
   
}

   
for(i = count -1; i >=0; i--){
       
if(i == count -1){
            printf
("%d", rev[i]);
       
}
       
else{
            printf
("->%d", rev[i]);
       
}
   
}
}

int main(){
   
int i, j;
   
int u, v, w;
    scanf
("%d",&N);
    memset
(matrix,0,sizeof(matrix));
   
while(1){
        scanf
("%d%d%d",&u,&v,&w);    
       
if(u ==-1&& v ==-1&& w ==-1){
           
break;    
       
}
        matrix
[u][v]= w;
   
}
   
for(i =0; i < N; i++){
       
for(j =0; j < N; j++){
           
if(i == j){
                matrix
[i][j]=0;    
           
}      
           
elseif(matrix[i][j]==0){
                matrix
[i][j]= INF;
           
}
       
}    
   
}
    dijkstra
(0);
   
for(i =1; i < N; i++){
        printf
("%d-->%d:%d\t",0, i, dist[i]);    
        print_path
(i);
        printf
("\n");
   
}
   
return0;    
}

[算法] dijkstra单源无负权最小路径算法

上一篇:Eclipse常用快捷键


下一篇:wpf 依赖属性实现原理(一种特殊的依赖属性)