㈠ 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语言版）最短路径算法 代码段：p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w]是什么意思
二维数组P中保存的是v0到各个点的最短路径。在v行中，值为true的列连起来，就是v0到v的最短路径。因为v0到w点的最短路径是v0到v的最短路径在加上<v,w>，所以w列先复制所有的v列的值，然后在将p[w][w]=true。此时w行中所有值为true列，就是v0到w的最短路径
㈢ 如何用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语言编写请简单点。用带权邻接矩阵输入一幅无向图，使用两种不同的算法计算出最短路径长度并输出路径。
//Floyed 实现赋权无向图定点对间的最短路径，时间复杂度O(n^3)
1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
#include<stdio.h>
int main()
{
int c[20][20],parth[20][20],i,j,k,t1,t2,t3,n,x,y,re;
printf("输入图的顶点数:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
printf("输入边(%d,%d)的权值,若不存在输入10000:",i,j);
scanf("%d",&c[i][j]);
}
}
如果是有向图就删掉这里"//for(i=1;i<=n;i++)
//{
///////////////////////////////////////for(j=1;j<=i;j++)
////////////////////////////////////////c[i][j]=c[j][i];
/////////////////////////////////////////}"
for(i=1;i<=n;i++)
c[i][i]=0;//自己到自己的权值为0
for(i=1;i<=n;i++) //初始化路径
{
for(j=1;j<=n;j++)
parth[i][j]=0;
}
for(k=1;k<=n;k++)//k是中间节点，i是起点j是中点。其实就是枚举中间节点，来求i j 的最短路径
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=10000&&t2!=10000&&(t3==10000||t1+t2<t3)) //松弛 覆盖原来的最短路
{c[i][j]=t1+t2,parth[i][j]=k;}//记录i j的中间点是k
}
}
}
while(1)//也可以用递归的形式输出parth
{
printf("输入2点:");
scanf("%d%d",&x,&y);
printf("最短距离为%d\n",c[x][y]);
printf("%d ",x);
re=y;
while(parth[x][y]!=0)
{
printf("%d ",parth[x][y]);
y=parth[x][y];
}
printf("%d\n",re);
}
return 0;
}