C语言最短路径

int main()

{

int G[100][100] = {}

//一个记录图的邻接矩阵

int a, b, w

//输入一共有7条边, 5个点

int i, j, k

for(i = 1i <= 5i++)

for(j = 1j <= 5j++)

G[i][j] = 9999999

for(i = 1i <= 7i++)

{

scanf("%d %d %d", &a, &b, &w)//输入每条边的信息，a和b代表这条边的两个顶点w代表两个点的距离

G[a][b] = w

G[b][a] = w

}

for(k = 1k <= 5k++)

for(i = 1i <= 5i++)

for(j = 1j <= 5j++)

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代替

如果你还不懂的话，就看一些关于图论的问题，这个最短路是图论中的一个经典题

＃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 = 1i <= ni++)

{

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 = 1i <ni++)

{

int temp = maxint

int u = v

//加入具有最小代价的邻居节点到s子集

for (j = 1j <= nj++)

{

if ((!s[j]) &&(dist[j] <temp))

{

u = j

temp = dist[j]

}

}

s[u] = 1

//计算加入新的节点后，更新路径使得其产生代价最短

for (j = 1j <= nj++)

{

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 = countj >= 1j--)

{

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 = 1i <= ni++)

{

cost[i]=(int *)malloc(sizeof(int)*(n+1))

}

//输入代价矩阵

for (j = 1j <= nj++)

{

for (t = 1t <= nt++)

{

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 = 1i <= 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)

}

}

}

#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=0di<4di++)

{

switch(di) //四个方向

{

case 0:i=Qu[front].i-1j=Qu[front].jbreak

case 1:i=Qu[front].ij=Qu[front].j+1break

case 2:i=Qu[front].i+1j=Qu[front].jbreak

case 3:i=Qu[front].ij=Qu[front].j-1break

}

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

}

---