데이터 구조 작은 작업 - 디 제 스 트 라 알고리즘 최 단 경로 구하 기

8429 단어 데이터 구조
v@[toc]
reference
code
void ShortestPath_DIJ(MGraph G, int v0)
{
	int n = G.vertexes;
	int v, i, w, min;
	bool S[MAX];
	int D[MAX];
	int path[MAX];
	//    
	for(v = 0; v < n; v++)
	{
		S[v] = false;//S       
		D[v] = G.arc[v0][v];// v0                   
		if(D[v] < INT_MAX) 
		{
			path[v] = v0;//  v0 v    ,  v    v0 
		}
		else
		{
			path[v] = -1;
		}
	}
	S[v0] = true;// v0  S
	D[v0] = 0;//         0 
	//     ,    v0     v     , v  s  
	for(i = 1; i < n; i++)
	{
		min = INT_MAX;
		//        
		for(w = 0; w < n; w++)
		{
			if(!S[w] && (D[w] < min)) 
			{
				v = w;
				min = D[w];
			}	
		}	
		S[v] = true;// v   S
		cout<<S[v];
		for(w = 0; w < n; w++)
		{
			if(!S[w] && ((D[v] + G.arc[v][w]) < D[w]))//           
			{
				D[w] = D[v] + G.arc[v][w];
				path[w] = v;//  w    v	
			}	
		} 
	} 
}

좋은 웹페이지 즐겨찾기