dijkstra算法:

/* 鄰接表存儲 - 無權圖的單源最短路算法 *//* dist[]和path[]全部初始化為-1 */ void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S ) {Queue Q;Vertex V;PtrToAdjVNode W;Q = CreateQueue( Graph->Nv ); /* 創建空隊列, MaxSize為外部定義的常數 */dist[S] = 0; /* 初始化源點 */AddQ (Q, S);while( !IsEmpty(Q) ){V = DeleteQ(Q);for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 對V的每個鄰接點W->AdjV */if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被訪問過 */dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距離更新 */path[W->AdjV] = V; /* 將V記錄在S到W->AdjV的路徑上 */AddQ(Q, W->AdjV);}} /* while結束*/ } /* 鄰接矩陣存儲 - 有權圖的單源最短路算法 */Vertex FindMinDist( MGraph Graph, int dist[], int collected[] ) { /* 返回未被收錄頂點中dist最小者 */Vertex MinV, V;int MinDist = INFINITY;for (V=0; V<Graph->Nv; V++) {if ( collected[V]==false && dist[V]<MinDist) {/* 若V未被收錄，且dist[V]更小 */MinDist = dist[V]; /* 更新最小距離 */MinV = V; /* 更新對應頂點 */}}if (MinDist < INFINITY) /* 若找到最小dist */return MinV; /* 返回對應的頂點下標 */else return ERROR; /* 若這樣的頂點不存在，返回錯誤標記 */ }bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S ) {int collected[MaxVertexNum];Vertex V, W;/* 初始化：此處默認鄰接矩陣中不存在的邊用INFINITY表示 */for ( V=0; V<Graph->Nv; V++ ) {dist[V] = Graph->G[S][V];if ( dist[V]<INFINITY )path[V] = S;elsepath[V] = -1;collected[V] = false;}/* 先將起點收入集合 */dist[S] = 0;collected[S] = true;while (1) {/* V = 未被收錄頂點中dist最小者 */V = FindMinDist( Graph, dist, collected );if ( V==ERROR ) /* 若這樣的V不存在 */break; /* 算法結束 */collected[V] = true; /* 收錄V */for( W=0; W<Graph->Nv; W++ ) /* 對圖中的每個頂點W *//* 若W是V的鄰接點并且未被收錄 */if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {if ( Graph->G[V][W]<0 ) /* 若有負邊 */return false; /* 不能正確解決，返回錯誤標記 *//* 若收錄V使得dist[W]變小 */if ( dist[V]+Graph->G[V][W] < dist[W] ) {dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */path[W] = V; /* 更新S到W的路徑 */}}} /* while結束*/return true; /* 算法執行完畢，返回正確標記 */ }

floyd算法:

/* 鄰接矩陣存儲 - 多源最短路算法 */bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] ) {Vertex i, j, k;/* 初始化 */for ( i=0; i<Graph->Nv; i++ )for( j=0; j<Graph->Nv; j++ ) {D[i][j] = Graph->G[i][j];path[i][j] = -1;}for( k=0; k<Graph->Nv; k++ )for( i=0; i<Graph->Nv; i++ )for( j=0; j<Graph->Nv; j++ )if( D[i][k] + D[k][j] < D[i][j] ) {D[i][j] = D[i][k] + D[k][j];if ( i==j && D[i][j]<0 ) /* 若發現負值圈 */return false; /* 不能正確解決，返回錯誤標記 */path[i][j] = k;}return true; /* 算法執行完畢，返回正確標記 */ }

總結

以上是生活随笔為你收集整理的dijkstra算法和floyd算法(C语言)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。