[算法] 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;    
}
上一篇:利用Team@OSC进行团队协作开发平台


下一篇:#2020征文-开发板# 用鸿蒙开发AI应用(三)软件篇