Ⅰ 如何用c语言来求最短路径
如果不考虑概率，可以使用Dijkstra算法
Ⅱ 急求！！用C语言求最短路径
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
const int MAXSIZE = 10;
const int HEAD = -1;
const int s = MAXSIZE * MAXSIZE;
struct TNode{
int x, y;
int parent;
};
int Metrix[MAXSIZE][MAXSIZE] = {
1, 1, 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1,
0, 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1,
0 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 1,
0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1,
0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1,
0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1,
0 , 1 , 1 ,1 , 0 , 1 , 0 , 0 , 0 , 1,
0 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1,
0 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0,
0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1
};
int A[MAXSIZE][MAXSIZE];
TNode List[s];
void Create()
{
/*int i, j;
for (i = 0; i < MAXSIZE; i++)
for (j = 0; j < MAXSIZE; j++)
Metrix[i][j] = 0;*/
}
TNode Move(int x, int y, const int &pos)
{
TNode aNode;
aNode.x = x;
aNode.y = y;
aNode.parent = pos;
return aNode;
}
void ExtendNode(const int &pos, int &Total, const int &method)
{
TNode aNode;
int x, y;
switch (method){
case 0: x = 0; y = -1; break;
case 1: x = 1; y = 0; break;
case 2: x = 0; y = 1; break;
case 3: x = -1; y = 0; break;
default: x = 0; y = 0; break;
}
x += List[pos].x;
y += List[pos].y;
if (A[x][y] || x < 0 || x >= MAXSIZE || y < 0 || y >= MAXSIZE || !Metrix[x][y])
return;
A[x][y] = 1;
Total++;
List[Total] = Move(x, y, pos);
}
int BFS(int x, int y, int tx, int ty)
{
const int TotalMethod = 4;
int i, j;
int pos, Total, method;
for (i = 0; i < MAXSIZE; i++)
for (j = 0; j < MAXSIZE; j++)
A[i][j] = 0;
List[0].x = x;
List[0].y = y;
List[0].parent = HEAD;
Total = 0;
pos = Total;
method = 0;
while (pos <= Total && (List[Total].x != tx || List[Total].y != ty) && Total <= s){
if (method < TotalMethod){
ExtendNode(pos, Total, method);
method++;
} else{
method = 0;
pos++;
}
}
if (List[Total].x == tx && List[Total].y == ty)
return Total;
else
return HEAD;
}
void Print()
{
int i, j;
for (i = 0; i < MAXSIZE; i++){
for (j = 0; j < MAXSIZE; j++)
if (Metrix[i][j] == 1)
cout << '*';
else
cout << '0';
cout << endl;
}
}
void PrintResult(const int &result)
{
int t;
int i, j;
if (result == HEAD)
cout << "No Way" << endl;
t = result;
while (t != HEAD){
Metrix[List[t].x][List[t].y] = 2;
t = List[t].parent;
}
for (i = 0; i < MAXSIZE; i++){
for (j = 0; j < MAXSIZE; j++)
if (Metrix[i][j] == 2)
cout << '*';
else
cout << '0';
cout << endl;
}
cout << endl;
}
void main()
{
int x, y, tx, ty;
int result;
Create();
Print();
cin >> x >> y >> tx >> ty;
result = BFS(x, y, tx, ty);
PrintResult(result);
getchar();
}
Ⅲ 最短路径函数 c语言
形参：源点、目标点的两个下标
返回值：两点之间距离的权值
Ⅳ C语言最短路径问题
其实50分是不够的；给点提示你可以使用图来解，这个试图的最短路径的查找。
把所有的甲、乙、丙、丁、戊都做成具有后续指针的节点，然后便利这张图，找到最短路径
Ⅳ C语言最短路径
int main()
{
int G[100][100] = {};
//一个记录图的邻接矩阵
int a, b, w;
//输入一共有7条边, 5个点
int i, j, k;
for(i = 1;i <= 5;i++)
for(j = 1;j <= 5;j++)
G[i][j] = 9999999;
for(i = 1;i <= 7;i++)
{
scanf("%d %d %d", &a, &b, &w);//输入每条边的信息，a和b代表这条边的两个顶点w代表两个点的距离
G[a][b] = w;
G[b][a] = w;
}
for(k = 1;k <= 5;k++)
for(i = 1;i <= 5;i++)
for(j = 1;j <= 5;j++)
if(G[i][j] > G[i][k] + G[k][j])
G[i][j] = G[i][k] + G[k][j];
printf("%d", G[1][4]);//输出两点之间的最短路，这里的两个点是3和5
return 0;
}
G[i][j]代表i到j的距离，甲，乙，丙，丁，戊用1，2，3，4，5代替
如果你还不懂的话，就看一些关于图论的问题，这个最短路是图论中的一个经典题
Ⅵ c语言最短路径问题。
这是图中任意二点的最短距离算法吧。 Floyd算法。
这程序太乱了。
num这个参数也不知道什么意思，反正就是Floyd算法。这个算法就是一个三层循环，数据结构的课本有说过，还有一些处理，就是最短距离的走法，课本都有说，网上也有，去参考下吧。
Ⅶ c语言求最短路径,这个程序都用到了什么
算法的中心思想就是判断row和col是否为偶数或同时为奇数
row %2 ==0代表row是偶数时,row %2 !=0代表row为奇数
Ⅷ 如何用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语言源代码】求最短路径,已确定起点终点和所有需要经过的点!!!
你就用上面找到的确定任意两点的算法找最短路径，再重复所有可能的两点，这样记录路径，就可以找到最短路径的两点了