當前位置：首頁 » 編程語言 » c語言最短路徑

c語言最短路徑

發布時間: 2021-03-05 00:32:28

㈠ 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語言實現求迷宮的最短路徑

#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定義迷宮，0表示能走的塊，1表示不能走，在外圍加上一圈不能走的塊
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct
{
int i,j; //塊的位置
int pre; //本路徑中上一塊在隊列中的下標
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索演算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四個方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循環
}
}
}
return 0;
}

void print(int n) //輸出路徑演算法
{
int k=n,j,m=1;
printf("\n");
do //將輸出的路徑上的所有pre改為-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宮最短路徑如下：\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}

㈢求圖的最短路徑 c語言

prim演算法或者kruskal演算法啊

㈣可運行的c語言程序：旅行商求最短路徑問題

在無向完全圖中，對於任意兩個頂點vi和vj，我們可以在多項式時間內找到版vi和vj這兩個權頂點之間的所有路徑，選擇其中路程最短的一條，令S[i,j]表示vi和vj這兩個頂點之間最短距離的那條路徑。搜索路徑S[i,j]，找到vi到達的在S[i,j]上的第一個頂點，記該頂點為vk，將其記錄在數組中R[][]，遞歸查找vi到vk和vk到vj的最短路徑及其相應權值，最後將數組D[]中的頂點和權值之和列印出來即為所求，並用畫圖函數將行經過程畫出。

㈤ C語言數組求最短路徑

#include <stdio.h>
#define M 5 /*行數*/
#define N 5 /*列數*/
#define MaxSize 100 /*棧最多元素個數*/
int mg[M+1][N+1]={ /*一個迷宮,其四周要加上均為1的外框*/
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct
{
int i;int j;int di;
} Stack[MaxSize],Path[MaxSize]; /*定義棧和存放最短路徑的數組*/
int top=-1; /*棧指針*/
int count=1; /*路徑數計數*/
int minlen=MaxSize; /*最短路徑長度*/
void mgpath() /*路徑為:(1,1)->(M-2,N-2)*/
{
int i,j,di,find,k;
top++; /*進棧*/
Stack[top].i=1;
Stack[top].j=1;
Stack[top].di=-1;mg[1][1]=-1; /*初始結點進棧*/
while (top>-1) /*棧不空時循環*/
{
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
if (i==M-1 && j==N-1) /*找到了出口,輸出路徑*/
{
printf("%4d: ",count++);
for (k=0;k<=top;k++)
{
printf("(%d,%d) ",Stack[k].i,Stack[k].j);
if ((k+1)%5==0) printf("\n\t"); /*輸出時每5個結點換一行*/
}
printf("\n");
if (top+1<minlen) /*比較找最短路徑*/
{
for (k=0;k<=top;k++)
Path[k]=Stack[k];
minlen=top+1;
}
mg[Stack[top].i][Stack[top].j]=0; /*讓該位置變為其他路徑可走結點*/
top--;
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
}
find=0;
while (di<4 && find==0) /*找下一個可走結點*/
{ di++;
switch(di)
{
case 0:i=Stack[top].i-1;j=Stack[top].j;break;
case 1:i=Stack[top].i;j=Stack[top].j+1;break;
case 2:i=Stack[top].i+1;j=Stack[top].j;break;
case 3:i=Stack[top].i,j=Stack[top].j-1;break;
}
if (mg[i][j]==0) find=1;
}
if (find==1) /*找到了下一個可走結點*/
{ Stack[top].di=di; /*修改原棧頂元素的di值*/
top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;/*下一個可走結點進棧*/
mg[i][j]=-1; /*避免重復走到該結點*/
}
else /*沒有路徑可走,則退棧*/
{
mg[Stack[top].i][Stack[top].j]=0; /*讓該位置變為其他路徑可走結點*/
top--;
}
}
printf("最短路徑如下:\n");
printf("長度: %d\n",minlen);
printf("路徑: ");
for (k=0;k<minlen;k++)
{
printf("(%d,%d) ",Path[k].i,Path[k].j);
if ((k+1)%5==0) printf("\n\t"); /*輸出時每5個結點換一行*/
}
printf("\n");
}
void main()
{
printf("迷宮所有路徑如下:\n");
mgpath();
}

㈥最短路徑演算法 C語言

為了不坑來害求知的少年，我源決定不給你寫代碼。去網上搜下關鍵字「任意節點最短路徑」，你會發現有無數的源碼。這些代碼基本上都源於兩個演算法：floyd演算法，Dijkstra演算法。
使用floyd演算法求最簡單，代碼大概8行左右，很簡單吧，呵呵，核心就是3個for循環而已。

㈦ C語言高手！！幫忙寫個最短路徑程序！！！！

這是我們的一個實驗，你可以參考一下
一、需求分析
【問題描述】
設計一個校園導遊程序，為來訪的客人提供各種信息查詢服務。
【基本要求】
（1）設計你所有學校的校園平面圖，所含景點不少於10個。以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。
（2）為來訪客人提供圖中任意景點相關信息的查詢。
（3）為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。
【測試數據】
由讀者根據實際情況指定。
二、概要設計
本次實驗中運用到的數據類型有：圖，頂點，邊結點
typedef struct edgenode
{
int adjvex; //臨接點序號
int length; //道路長度
char name[20]; //景點名稱
char info[100]; //景點詳細信息
struct edgenode *next;
}edgenode, *Node ;
typedef struct
{
char data[20]; //存儲景點的名稱.
char str[100]; //具體的介紹此景點
struct edgenode *link; //指向下一個景點
}vexnode; //景點及其信息.
typedef struct Edge
{
int lengh; //邊的權值，表示路徑長度.
int ivex, jvex; //邊的兩端頂點號
struct Edge *next; //指向下一條邊
} EdgeType; //邊及其信息.
typedef struct
{
int num; //頂點編號
char data[20]; //頂點名稱
} vertex;
typedef struct{
vertex vexs[MAX]; //頂點集合
int edges[MAX][MAX]; //鄰接矩陣
}adjmax;
基本操作：
void fun();
//操作結果：功能說明並顯示所有景點
void creatgraph(vexnode g[],int &n, EdgeType e[],adjmax &adj);
//操作結果：創建校園圖
void travgraph(vexnode g[],int n,adjmax adj);
//初始條件：已知鄰接表adj和頂點g及其數目n
//操作結果：查找指定景點信息
void Ppath(int path[][MAX],int i,int j,vexnode g[]);
//操作結果：尋找最短路徑
void Dispath(int A[][MAX],int path[][MAX],int n,vexnode g[]);
//初始條件：已知頂點g和數目n及其權值
//操作結果：顯示最短路徑
void Floyd(adjmax adj,int n,vexnode g[]);
//初始條件：已知鄰接表adj和頂點g
//操作結果：Floyd演算法計算所有兩個景點間最短路徑
三、詳細設計
1、---------main()---------
char choice;
int n = 0; / /景點數目
vexnode g[MAX]; //保存頂點及其信息
EdgeType e[MAXedg]; //保存邊及其信息
adjmax adj; //保存邊和定點

creatgraph(g,n,e,adj); //建立校園導游圖
while(1)
{
do{
system("cls");
fun(); //功能說明
printf("請輸入所要進行的操作：");
choice=getch();
printf("\n"); }while(choice!='s'&&choice!='S'&&choice!='v'&&choice!='V'&&choice!='Q'&&choice!='q');
switch(choice)
{
case('s'):
case('S'): Floyd(adj,n,g); //查找最短路徑
break;
case('v'):
case('V'):travgraph(g,n,adj); //景點查詢
break;
case('q'):
case('Q'):return; //結束程序
}
}
2、------- travgraph()---------
void travgraph(vexnode g[],int n,adjmax adj)
{
int i = 1,flag = 1,num; //num存儲要查詢的景點的序號
char ch;
edgenode *p;
printf("請輸入您要查詢的景點序號:\n");
scanf("%d",&num);
while(i <= n) //遍歷鄰接表
{
p = g[i].link;
if(i == num && flag == 1)
{
printf("此景點的名稱是: %s\n",g[i].data);
printf("此景點的介紹是: %s\n",g[i].str);
printf("是否繼續? Y/N");
ch=getch();
printf("\n");
if(ch == 'Y' || ch == 'y') //繼續
{
flag = 1;
i = 1;
printf("請輸入您要查詢的景點序號:\n");
scanf("%d",&num);
getchar();
}
else
flag = 0; //不繼續
}
else
i++;
}
}3、------- Floyd()---------
//Floyd演算法計算所有兩個景點間最短路徑
void Floyd(adjmax adj,int n,vexnode g[])
{
int A[MAX][MAX],path[MAX][MAX]; //A是路徑長度，path是路徑。
int i,j,k;
for(i = 1; i <= n; i++) //初始化
for(j = 1; j <= n; j++)
{
A[i][j] = adj.edges[i][j]; //i j之間長度
if(i == j)
{
A[i][j] = 0;
}
path[i][j] = -1; //初始化
}
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
if(A[i][j] > (A[i][k] + A[k][j]))
{
A[i][j] = A[i][k]+A[k][j]; //修改最短路徑長度值
path[i][j] = k; //將最短路徑的節點號保存
}
}
Dispath(A,path,n,g); //用戶輸入，查找任意兩個景點間的最短路徑。
}

㈧ C語言如何實現5個城市之間求最短路徑。從A出發，最終回到A。求最短路徑問題。可用窮舉來完成。

//這個演算法名字叫迪傑斯特拉演算法
#include<stdio.h>
#include<stdlib.h>
#definemax11000000000
inta[1000][1000];
intd[1000];//d表示某特定邊距離
intp[1000];//p表示永久邊距離
inti,j,k;
intm;//m代表邊數
intn;//n代表點數
intmain()
{
scanf("%d%d",&n,&m);
intmin1;
intx,y,z;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
a[y][x]=z;
}
for(i=1;i<=n;i++)
d[i]=max1;
d[1]=0;
for(i=1;i<=n;i++)
{
min1=max1;
for(j=1;j<=n;j++)
if(!p[j]&&d[j]<min1)
{
min1=d[j];
k=j;
}
p[k]=j;
for(j=1;j<=n;j++)
if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
d[j]=d[k]+a[k][j];
}
for(i=1;i<n;i++)
printf("%d->",p[i]);
printf("%d
",p[n]);
return0;
}

㈨求用 C語言寫一個輸出路徑和最短路徑的例子！！

閱讀全文

c語言最短路徑

與c語言最短路徑相關的閱讀推薦