交通最短路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语言编程最短路问题（其中，各个点之间的距离是用键盘写入的） 急求！！！！！

之前写过一个一样的......