交通最短路c語言編程

A. c語言實現最短路問題的演算法

＃i nclude<stdio.h>
＃i nclude <stdlib.h>
//Dijkstra演算法實現函數
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);
}
}
}

B. 最短路徑演算法 C語言

#include<stdio.h>

#defineMAXNODE108

intpath[MAXNODE+1][MAXNODE+1]={0};

intmain(void)
{
FILE*fpr,*fpw;
intva,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];
elseif(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);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw,"
");
}

return0;
}

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

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

-1表示不通。

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

C. c語言最短路問題編程 最短路我通過excel的線性規劃算出 圖中數字是路程

這個沒問題，請問是給出出發點和結束點然後求兩點的最短路嗎？可以用SPFA演算法或者dijkstra演算法。

D. 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); //用戶輸入，查找任意兩個景點間的最短路徑。
}

E. 用C語言編程最短路問題（其中，各個點之間的距離是用鍵盤寫入的） 急求！！！！！

之前寫過一個一樣的......