【図】最短パスDijkstraアルゴリズムC言語実装

22038 ワード
図 Data_Structure 最短パス
Dijkstraアルゴリズム(単一ソースポイントパスアルゴリズム)要件:図に負の重み値エッジが存在しない)
アルゴリズムステップは、G={V,E}
  • 初期時令S=V 0,T=V−S=S=V 0,T=V−S=S=V 0,T=V=S=V 0,T=V−S={残りの頂点},Tにおける頂点に対応する距離値が,d(V 0,V i),d(V 0,Vi), d(V 0,Vi)が弧上の重み値が,d(V 0,V i)d(V 0,V 0,V i)d(V 0,Vi)d(V 0,Vi)が=d(V 0,V i)=d(V 0,Vi)=d(V 0,Vi)が存在する場合、=d(V 0,V i)=d(V 0,Vi)=d(V 0,Vi)=d(図面なし)注:図面にはこのステップは必要ありません.
  • TからSの頂点に関連付けられたエッジを持つ重み値が最も小さい頂点Wを選択し、Sの
    • に加える.
  • 残りのTの頂点の距離値を修正する:Wを中間頂点として加え、V 0からViまでの距離値を短くすると、Sにすべての頂点、すなわちW=V i W=Vi W=Viが含まれるまで、この距離値を修正して上記ステップ2、3を繰り返す.
    コード実装:
    #include
  
#define SIZE 110  
#define INF 10000000
  
 
int dijkstra(int from, int to,int map[SIZE][SIZE],int n,int m){	//        
	
    int i,j;  
    int START =from;
    int parent[SIZE];
    int len[SIZE];  	//d[i]     i       
    int visit[SIZE];  //        
    for(int i =0;i<SIZE;i++)
       parent[i]=START;
    
    for(i = 1 ; i <= n  ; i ++){	//    
        visit[i] = 0;	//            
        len[i] = map[from][i];	//             
    }  
   
    for(i = 1 ; i <= n ; ++i){	//                
        int min = INF;  //    len[i] 
        int pos;  //   len[i]    
  
        for(j = 1 ; j <= n ; ++j)
        {	
            if(!visit[j] && min > len[j]){  
                pos = j;  
                min = len[j];  
            }  
        }  
        visit[pos] = 1;  
  
        for(j = 1 ; j <= n ; ++j){
            if(!visit[j] && (len[j] > (len[pos] +map[pos][j])))
            { //  j        &&j           >pos           +pos   j       
                len[j] = len[pos] + map[pos][j];	//  j           
                parent[j]=pos;	//      
            }  
        }  
    }  
    for(i=1;i<=n;i++)
    {
        if(i!=from)
         printf("the parent of %d is %d 
    "    ,i,parent[i]);
    }

    return len[to];
}
void gen(int map[SIZE][SIZE],int vertex_num,int edge_num)
{
    int i,j;
    int k;
    int Ver;
    int start,end;
    
    for(i=0;i<=vertex_num;i++)
    {
        for(j=0;j<=vertex_num;j++)
         map[i][j] = INF;
    }

    for(k=0;k<edge_num;k++)
    {
        scanf("%d%d",&i,&j);
        scanf("%d",&map[i][j]);
        map[j][i] = map[i][j];
    }
}
  
int main () {  
 
    int map[SIZE][SIZE]; 
    int vertex_num; 
    int edge_num;
    int start,end;
    scanf("%d%d",&start,&end);
    scanf("%d%d",&vertex_num,&edge_num);
    
    gen(map,vertex_num,edge_num);

     int ans = dijkstra(start,end,map,vertex_num,edge_num);

     printf("ans = %d",ans);

    return 0;  
}

    テストデータ:入力:
    1 5//  1 5     
6 9//    ，   

1 2 7
1 3 9 
1 6 14
2 3 10
2 4 15
5 6 9
3 6 2
4 5 6
3 4 11

    後の9行は
        map[1][2] = 7;	//     
	map[1][3] = 9;
	map[1][6] = 14;
	map[2][3] = 10;
	map[2][4] = 15;
	map[3][6] = 2;
	map[5][6] = 9;
	map[4][5] = 6;
	map[3][4] = 11;

    出力:
    the parent of 2 is 1
the parent of 3 is 1
the parent of 4 is 3
the parent of 5 is 6
the parent of 6 is 3
shortest path = 20
    • Python FAQ集錦
    python文字列をjsonオブジェクトに変換して値をとる