求解矩陣最小路徑和問題c語言,c語言求矩陣中最大值最小值及位置

本文目錄一覽：

• 1、怎麼用c語言實現單源最短路徑問題？要求是用Dijkstra算法，最好寫出所有的代碼 ，包括結構定義等等，對一
• 2、C語言最短路徑
• 3、c語言數據結構 最短路徑問題代碼
• 4、c語言編程求矩陣的最大值，最小值及所在的位置
• 5、用dijkstra算法解決最短路徑問題c語言代碼實現時怎樣將每一個路徑的頂點次序依次輸出出來？
• 6、c語言最短路徑問題。

怎麼用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

C語言最短路徑

int main()

{

int G[100][100] = {};

//一個記錄圖的鄰接矩陣

int a, b, w;

//輸入一共有7條邊, 5個點

int i, j, k;

for(i = 1;i = 5;i++)

for(j = 1;j = 5;j++)

G[i][j] = 9999999;

for(i = 1;i = 7;i++)

{

scanf(“%d %d %d”, a, b, w);//輸入每條邊的信息，a和b代表這條邊的兩個頂點w代表兩個點的距離

G[a][b] = w;

G[b][a] = w;

}

for(k = 1;k = 5;k++)

for(i = 1;i = 5;i++)

for(j = 1;j = 5;j++)

if(G[i][j] G[i][k] + G[k][j])

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

printf(“%d”, G[1][4]);//輸出兩點之間的最短路，這裡的兩個點是3和5

return 0;

}

G[i][j]代表i到j的距離，甲，乙，丙，丁，戊用1，2，3，4，5代替

如果你還不懂的話，就看一些關於圖論的問題，這個最短路是圖論中的一個經典題

c語言數據結構 最短路徑問題代碼

直接看代碼：

#include stdlib.h

#define MAXVEX 10

typedef struct graph{

    int n,e;//頂點數、邊數

    char vexs[MAXVEX];//頂點數組

    int arcs[MAXVEX][MAXVEX];//鄰接矩陣

    int kind;//類型：0有向圖；1無向圖；2有向網；3無向網

} MGraph;

void PrintPath(MGraph G,int *p,int i){

    if(p[i]=0){

        PrintPath(G,p,p[i]);//先輸出前驅頂點

    }

    printf(“%c”,G.vexs[i]);//輸出本頂點

}

void Dijkstra(MGraph G, int v){

    //用Dijkstra算法求有向網G中序號為v的頂點到

    //其餘各頂點的最短路徑

    int *s,*d,*p,i,j,k,min;

    if(v0||v=G.n){//頂點編號參數錯誤

        printf(“Dijkstra parameter ERROR! v0 Or v=%d”,G.n);

        return;

    }

    s=(int *)malloc(sizeof(int)*G.n);

    d=(int *)malloc(sizeof(int)*G.n);

    p=(int *)malloc(sizeof(int)*G.n);

    for(i=0;iG.n;i++){ //初始化輔助數組，置0

        s[i]=0;d[i]=G.arcs[v][i];

        if(d[i]!=0)p[i]=v; //v是vi的直接前驅

        else p[i]=-1; //-1表示無直接前驅

    }

    s[v]=1;d[v]=0; //確定源點自身的最短路徑長度

    printf(“Dijkstra: (The shortest path from %c:)\n”,G.vexs[v]);

    for(i=0;iG.n-1;i++){

        //確定v到其餘n-1個頂點的最短路徑

        min=32767;k=-1;

        for(j=0;jG.n;j++){

            //找出路徑長度最小的頂點k

            if(!s[j]d[j]!=0d[j]min){

                k=j; min=d[k];

            }

        }

        if(k0){//有未能到達的頂點，把它們輸出

            for(j=0;jG.n;++j){

                if(j==v)continue;

                if(s[j]==0){

                    printf(“%c-%c: No path.\n”,G.vexs[v],G.vexs[j]);

                }

            }

            free(s); free(d); free(p);

            return; //已完成或出現不連通的頂點

        }

        s[k]=1;

        printf(“%c-%c: d=%-5d, p=”,G.vexs[v],G.vexs[k],d[k]);

        PrintPath(G,p,k);//輸出v到i的路徑（正序）

        printf(“\n”);

        for(j=0;jG.n;j++){

            //更新其餘頂點的最短路徑及前驅

            if(!s[j]G.arcs[k][j]!=0(d[j]==0||d[j]d[k]+G.arcs[k][j])){

                d[j]=d[k]+G.arcs[k][j]; p[j]=k;

            }

        }

    }

    free(s); free(d); free(p);

}

這是單源的最短路徑算法。

c語言編程求矩陣的最大值，最小值及所在的位置

#includestdio.h

int a[9][9]={{5,15,9,16,7,10,2,6,3,20}};

//最大值函數聲明

int getmax(int *,int *);

//最小值函數聲明

int getmin(int *,int *)

//主函數

void main(void)

{

int imax,jmax,imin,jmin;

printf(“矩陣最大值為%d,位置為%d行，%d列；”,getmax(imax,jmax),imax,jmax);

printf(“最小值為%d，位置為%d行，%d列;”,getmin(imin,jmin),imin,jmin);

printf(“正對角線和為%d!”,getlsum());

printf(“反對角線和為%d!”,getrsum());

}

//求最大值函數

int getmax(int * imax,int * jmax)

{

int max=0;

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

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

{

if(a[i][j]max)

{

*imax=i;

*jmax=j;

max=a[i][j];

}

}

return max;

}

//求最小值函數

int getmin(int * imin,int * jmin)

{

int min=65535;

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

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

{

if(a[i][j]min)

{

*imin=i;

*jmin=j;

min=a[i][j];

}

}

return min;

}

//求正對角線和函數

int getlsum()

{

int sum=0;

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

sum+=a[i][i];

return sum

}

//求反對角線和函數

int getrsum()

{

int sum=0;

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

sum+=a[i][9-i];

return sum;

}

程序寫好了，放在一起的，公用一個主函數，如果不要顯示哪個功能就把哪塊幹掉，如果這你都不會我就沒辦法了！！！

用dijkstra算法解決最短路徑問題c語言代碼實現時怎樣將每一個路徑的頂點次序依次輸出出來？

void Dijkstra(int n,int v,int dist[],int prev[],int **cost)

{

  int i;

  int j;

    int maxint = 65535;//定義一個最大的數值，作為不相連的兩個節點的代價權值

    int *s ;//定義具有最短路徑的節點子集s

  s = (int *)malloc(sizeof(int) * n);

    //初始化最小路徑代價和前一跳節點值

    for (i = 1; i = n; i++)

    {

        dist[i] = cost[v][i];

        s[i] = 0;

        if (dist[i] == maxint)

        {

            prev[i] = 0;

        }

        else

        {

            prev[i] = v;

        }

    }

    dist[v] = 0;

    s[v] = 1;//源節點作為最初的s子集

    for (i = 1; i  n; i++)

    {

        int temp = maxint;

        int u = v;

        //加入具有最小代價的鄰居節點到s子集

        for (j = 1; j = n; j++)

        {

            if ((!s[j])  (dist[j]  temp))

            {

                u = j;

                temp = dist[j];

            }

        }

        s[u] = 1;

        //計算加入新的節點後，更新路徑使得其產生代價最短

        for (j = 1; j = n; j++)

        {

            if ((!s[j])  (cost[u][j]  maxint))

            {

                int newdist = dist[u] + cost[u][j];

                if (newdist  dist[j])

                {

                    dist[j] = newdist;

                    prev[j] = u;

                }

            }

        }

    }

}

//展示最佳路徑函數

void ShowPath(int n,int v,int u,int *dist,int *prev)

{

 int j = 0;

 int w = u;

 int count = 0;

 int *way ;

 way=(int *)malloc(sizeof(int)*(n+1));

 //回溯路徑

 while (w != v)

 {

  count++;

  way[count] = prev[w];

  w = prev[w];

 }

 //輸出路徑

 printf(“the best path is:\n”);

 for (j = count; j = 1; j–)

 {

  printf(“%d – “,way[j]);

 }

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

}

//主函數，主要做輸入輸出工作

void main()

{

 int i,j,t;

  int n,v,u;

 int **cost;//代價矩陣

 int *dist;//最短路徑代價

 int *prev;//前一跳節點空間

 printf(“please input the node number: “);

  scanf(“%d”,n);

  printf(“please input the cost status:\n”);

 cost=(int **)malloc(sizeof(int)*(n+1));

  for (i = 1; i = n; i++)

  {

      cost[i]=(int *)malloc(sizeof(int)*(n+1));

  }

  //輸入代價矩陣

  for (j = 1; j = n; j++)

  {

      for (t = 1; t = n; t++)

      {

          scanf(“%d”,cost[j][t]);

      }

  }

  dist = (int *)malloc(sizeof(int)*n);

  prev = (int *)malloc(sizeof(int)*n);

  printf(“please input the source node: “);

  scanf(“%d”,v);

  //調用dijkstra算法  

  Dijkstra(n, v, dist, prev, cost);

  printf(“*****************************\n”);

 printf(“have confirm the best path\n”);

 printf(“*****************************\n”);

 for(i = 1; i = n ; i++)

 {

  if(i!=v)

  {

   printf(“the distance cost  from node %d to node %d is %d\n”,v,i,dist[i]);

   printf(“the pre-node of node %d is node %d \n”,i,prev[i]);

   ShowPath(n,v,i, dist, prev);

  }

 }

}

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;

}