路徑優化c語言,路徑優化的方法

本文目錄一覽：

• 1、c語言最短路徑問題。
• 2、C語言暢通工程
• 3、最短路徑演算法 C語言
• 4、一道C語言棋盤最優路徑的題目，求教
• 5、怎麼用c語言實現單源最短路徑問題？要求是用Dijkstra演算法，最好寫出所有的代碼 ，包括結構定義等等，對一

c語言最短路徑問題。

#include stdio.h

#define N 7 /* 頂點數目 */

#define I 999 /* 表示無窮大 */

int graph[N][N] = { /* 圖的鄰接矩陣 */

{I, 4, 5, 8, I, I, I},

{I, I, I, 6, 6, I, I},

{I, I, I, 5, I, 7, I},

{I, I, I, I, 8, 9, 9},

{I, I, I, I, I, I, 5},

{I, I, I, I, I, I, 4},

{I, I, I, I, I, I, I}

};

int List[N]; /* 存放拓撲序列 */

int TopologicalOrder(); /* 拓撲排序函數 */

void main() /* 主 函 數 */

{

int i, j, k, l;

int ee[N], el[N]; /* 最長最短距離 */

int path_e[N][N], path_l[N][N], n_e[N], n_l[N]; /* 記錄路徑數據 */

/* 初始化數據 */

for (i = 0; i N; i++) {

n_e[i] = 0; /* 到 i 的最短路線的結點數 */

n_l[i] = 0; /* 到 i 的最長路線的結點數 */

ee[i] = I;

el[i] = 0;

}

ee[0] = el[0] = 0; /* 初始化頭結點 */

path_e[0][0] = 0;

path_l[0][0] = 0;

n_e[0] = 1;

n_l[0] = 1;

/* 拓撲排序 */

if (!TopologicalOrder())

return;

/* 對於拓撲序列,運用動態規劃步步算出最長路線與最短路線 */

for (i = 0; i N; i++) {

/* 提取拓撲序列的元素 */

k = List[i];

/* 更新它所指向頂點的所有數據 */

for (j = 0; j N; j++) {

/* 尋找指向的頂點 */

if (graph[k][j] != I) {

/* 如果新路徑更短 */

if (graph[k][j] + ee[k] ee[j]) {

/* 更新最短路徑長度 */

ee[j] = graph[k][j] + ee[k];

/* 更新最短路線 */

for (l = 0; l n_e[k]; l++) {

path_e[j][l] = path_e[k][l];

}

path_e[j][l] = j;

n_e[j] = l + 1;

}

/* 如果新路徑更長 */

if (graph[k][j] + el[k] el[j]) {

/* 更新最長路徑長度 */

el[j] = graph[k][j] + el[k];

/* 更新最長路線 */

for (l = 0; l n_l[k]; l++) {

path_l[j][l] = path_l[k][l];

}

path_l[j][l] = j;

n_l[j] = l + 1;

}

}

}

}

/* 輸出結果到屏幕 */

for (i = 0; i N; i++) {

printf(“shortest(%d): %2d Path: “, i + 1, ee[i]);

for (j = 0; j n_e[i]; j++) {

printf(“%d “, path_e[i][j] + 1);

}

printf(“\n”);

printf(“longest (%d): %2d Path: “, i + 1, el[i]);

for (j = 0; j n_l[i]; j++) {

printf(“%d “, path_l[i][j] + 1);

}

printf(“\n”);

}

}

int TopologicalOrder()

{

int i, j, top, count;

int indegree[N], Stack[N];

top = 0; /* 棧頂標誌 */

for (i = 0; i N; i++) {

indegree[i] = 0; /* 初始化入度 */

for (j = 0; j N; j++) {

if (graph[j][i] != I) { /* 如連通 */

indegree[i]++; /* 入度自增1 */

}

}

if (!indegree[i]){ /* 如入度為零 */

Stack[top++] = i; /* 入棧 */

}

}

count = 0; /* 輸出頂點數 */

while (top != 0) {

i = Stack[–top];

List[count++] = i;

for (j = 0; j N; j++) {

if (graph[i][j] != I) { /* 如連通 */

if (!(–indegree[j])) { /* 而且入度為零 */

Stack[top++] = j; /* 入棧 */

}

}

}/* for */

}/* while */

return (count N) ? 0 : 1;

}

C語言暢通工程

//是最小生成樹演算法

#includestdio.h

#includestring.h

const int INF=1000000000;

const int MAX=105;

int map[MAX][MAX],cost[MAX];

bool used[MAX];

int MST(int n)

{

int i,j,k,min_;

int ret=0;

memset(used,false,sizeof(used));

for(i=0;in;i++)

cost[i]=map[0][i];

cost[0]=0;

for(i=0;in;i++)

{

k=-1;

min_=INF;

for(j=0;jn;j++)

{

if(!used[j]cost[j]min_)

{

k=j;

min_=cost[j];

}

}

used[k]=true;

ret+=cost[k];

for(j=0;jn;j++)

{

if(!used[j]map[k][j]cost[j])

cost[j]=map[k][j];

}

}

return ret;

}

int main()

{

int n,i,j;

int a,b,c;

while(scanf(“%d”,n)!=EOFn)

{

for(i=0;in;i++)

for(j=0;jn;j++)

map[i][j]=INF;

for(i=0;i(n-1)*n/2;i++)

{

scanf(“%d%d%d”,a,b,c);

a–;

b–;

if(map[a][b]c)map[a][b]=map[b][a]=c;

}

printf(“%d\n”,MST(n));

}

return 0;

}

最短路徑演算法 C語言

#include stdio.h

#define MAXNODE 108

int path[MAXNODE + 1][MAXNODE + 1] = {0};

int main(void)

{

  FILE *fpr, *fpw;

  int va, vb, i, j, k;

  fpr = fopen(“in.txt”, “r”); /* 讀取的文件名稱in.txt */

  fpw = fopen(“out.txt”, “w”); /* path的數據在out.txt中展現 */

  while (fscanf(fpr, “%d%d”, va, vb) != EOF)

    path[va][vb] = path[vb][va] = 1;

  for (k = 1; k = MAXNODE; ++k) {

    for (i = 1; i = MAXNODE; ++i) {

      for (j = 1; j = MAXNODE; ++j) {

        if (!path[i][k] || !path[k][j])

          continue;

        if (!path[i][j])

          path[i][j] = path[i][k] + path[k][j];

        else if (path[i][j]  path[i][k] + path[k][j])

          path[i][j] = path[i][k] + path[k][j];

      }

    } 

  }

  for (i = 1; i = MAXNODE; ++i) {

    for (j = 1; j = MAXNODE; ++j) {

      if (i == j)

        fprintf(fpw, “%-10d”, 0);

      else if (path[i][j])

        fprintf(fpw, “%-10d”, path[i][j]);    

      else 

        fprintf(fpw, “%-10d”, -1);  

    }

    fprintf(fpw, “\n”);

  }

  return 0;

}

注意：floyd演算法中k為最外層，這是動態規劃的思想，不能改變i,j,k的順序！！！

這是之前的答案的錯誤之處。

-1表示不通。

具體程序分析，我可以加你QQ，願意的話，你把QQ寫給我。

一道C語言棋盤最優路徑的題目，求教

這題還是有點意思的。

正如diordna所說，因為涉及到全局最優，

大小又是1000×1000，感覺廣搜有點困難，所以打算試試DP。。

思路如下，不知道對不對。。

Part.1

設map[i][j]保存棋盤格子的價值 (i = 0..n-1, j = 0..m-1)

設f[i][j][k]記錄棋盤(i, j)位置的最大價值和 (i = 0..n-1, j = 0..m-1, k = 0,1,2)

k表示這個位置是怎麼來的：

k = 0: 左→右

k = 1: 上→下

k = 2: 下→上

首先初始化 f[i][j][k] = -inf

然後根據題意有：f[0][0][k] = map[0][0], k = 0,1,2

Part.2

又因為不能向左走，實際上就是說第j = 0列的格子只能向下走

所以可以先把f[i][0][1]算出來

f[i][0][1] = max(k=0,1){f[i-1][0][k]} + map[0][j] = f[i-1][0][1] + map[i][0], i = 1..n-1

Part.3

然後考慮任意一個非第0列的格子(i, j), i = 0..n-1, j = 1..m-1

便于思考特殊化一下，假設考慮第j = 1列（當然其它列也一樣），

任意一個格子有3種到達方式，分別對應k = 0, 1, 2

但此時我們只知道每個格子的左邊格子里的f值

那麼我們先計算k=0時刻各格子的f值 (左→右)

f[i][j][0] = max(k=0,1,2){f[i][j-1][k]} + map[i][j], i = 0..n-1, j = 1

Part.4

這樣一來各個格子從左邊來到後的總價值f就得到了

接下來處理從上到下和從下到上的情況

由於從某個格子開始一旦選擇從上到下或從下到上走後就無法回頭了

不妨從上到下開始：

f[i][j][1] = max(k=0,1){f[i-1][j][k]} + map[i][j], i = 1..n-1, j = 1

然後從下到上：

f[i][j][2] = max(k=0,2){f[i+1][j][k]} + map[i][j], i = n-2..0, j = 1

Part.5

這樣一來每個格子對應的3種走法的價值最大值就能得到了

如此回到Part.3循環列j = 1..m-1

最後只要取max(k=0,1){f[n-1][m-1][k]} 即可得到最優路徑價值和

試著寫了一下，不知道能不能過。。

注意由於開了1000×1000的long數組，所以VC調試的時候注意把堆棧開大一點

#include iostream

using namespace std;

#define MAXN 1000

#define INF 0x7fffffff

long map[MAXN][MAXN];

long f[MAXN][MAXN][3];

long getmax(long a, long b){ return (a  b) ? a : b;}

void init()

{

 for(int i = 0; i  MAXN; i++)

 {

  for(int j = 0; j  MAXN; j++)

  {

   map[i][j] = -INF;

   f[i][j][0] = -INF;

   f[i][j][1] = -INF;

   f[i][j][2] = -INF;

  }

 }

}

int main()

{

 // Part.1

 int n, m;

 cin  n  m;

 init();

 for(int i=0; in; i++)

 {

  for(int j=0; jm; j++)

  {

   cin  map[i][j];

  }

 }

 f[0][0][0] = f[0][0][1] = f[0][0][2] = map[0][0];

 // Part.2

 for(int i=1; in; i++)

 {

  f[i][0][1] = f[i-1][0][1] + map[i][0];

 }

 for(int j=1; jm; j++)

 {

  // Part.3

  for(int i=0; in; i++)

  {

   long max = getmax(getmax(f[i][j-1][0], f[i][j-1][1]), f[i][j-1][2]);

   if(max == -INF) continue;

   f[i][j][0] = max + map[i][j];

  }

  // Part.4

  for(int i=1; in; i++)

  {

   long max = getmax(f[i-1][j][0], f[i-1][j][1]);

   if(max == -INF) continue;

   f[i][j][1] = max + map[i][j];

  }

  for(int i=n-2; i=0; i–)

  {

   long max = getmax(f[i+1][j][0], f[i+1][j][2]);

   if(max == -INF) continue;

   f[i][j][2] = max + map[i][j];

  }

 }

 cout  getmax(f[n-1][m-1][0], f[n-1][m-1][1])  endl;

 return 0;

}

怎麼用c語言實現單源最短路徑問題？要求是用Dijkstra演算法，最好寫出所有的代碼 ，包括結構定義等等，對一

C語言代碼：//清華大學出版社光碟的代碼

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D)

{ // 演算法7.15

// 用Dijkstra演算法求有向網G的v0頂點到其餘頂點v的最短路徑P[v]

// 及其帶權長度D[v]。

// 若P[v][w]為TRUE，則w是從v0到v當前求得最短路徑上的頂點。

// final[v]為TRUE當且僅當v∈S,即已經求得從v0到v的最短路徑。

int i=0,j, v,w,min;

bool final[MAX_VERTEX_NUM];

for (v=0; vG.vexnum; ++v) {

final[v] = FALSE;

D[v] = G.arcs[v0][v].adj;

for (w=0; wG.vexnum; ++w) P[v][w] = FALSE; // 設空路徑

if (D[v] INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }

}

D[v0] = 0; final[v0] = TRUE; // 初始化，v0頂點屬於S集

//— 開始主循環，每次求得v0到某個v頂點的最短路徑，並加v到S集 —

for (i=1; iG.vexnum; ++i) { // 其餘G.vexnum-1個頂點

min = INFINITY; // 當前所知離v0頂點的最近距離

for (w=0; wG.vexnum; ++w)

if (!final[w]) // w頂點在V-S中

if (D[w]min) { v = w; min = D[w]; } // w頂點離v0頂點更近

final[v] = TRUE; // 離v0頂點最近的v加入S集

for (w=0; wG.vexnum; ++w) // 更新當前最短路徑及距離

if (!final[w] (min+G.arcs[v][w].adjD[w])) {

// 修改D[w]和P[w], w∈V-S

D[w] = min + G.arcs[v][w].adj;

for(j=0;jG.vexnum;j++) P[w][j] = P[v][j]; //第v行賦值於第w行

P[w][w] = TRUE; // P[w] = P[v]+[w]

}//if

}//for

} // ShortestPath_DIJ