Ⅰ 如何用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語言源代碼】求最短路徑,已確定起點終點和所有需要經過的點!!!
你就用上面找到的確定任意兩點的演算法找最短路徑，再重復所有可能的兩點，這樣記錄路徑，就可以找到最短路徑的兩點了