＃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)
}
}
}
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代替
如果你还不懂的话，就看一些关于图论的问题，这个最短路是图论中的一个经典题
