C语言实现最短路问题的算法

＃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)

}

}

}

因为a,b,c都等于0,a++是先运算后自增,所以a++与++b或c++等于0与++b或c++

又因为逻辑运算短路(也就是当0与任何表达式时,将不进行后面的表达式计算,直接得出结果为0,

当1或任何表达式时,将不进行后面的表达式计算,直接得出结果为1)所以++b被跳过,没有执行,

因此a++与++b或c++的表达式的值等于0与++b或0等于0,因为a++和c++执行运算后自增1,

所以执行a++与++b或c++表达式后a=1,c=1,++b因为没有被执行所以b仍然为初始值0.

验证程序如下

---