当前位置：首页 » 编程语言 » 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语言最短路径相关的阅读推荐