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)

}

}

}

#include <iostream>

/************************************************************************/

/* 编一个简单的win32程序，提示输入电压，电阻，能够计算电流。

还能进行输入纠错。就是输负数就让你重新输入。考虑短路情况 */

/************************************************************************/

using namespace std

int main()

{

float U,R,I

cout<<"请输入电压U："<<endl

do{cin>>Uif (U<0)

{cout<<"输入电压不能为负！"<<endl

}

}while(U<0)

cout<<"请输入电阻R："<<endl

do{cin>>Rif (R<0)

{cout<<"输入电阻不能为负！"<<endl

}

} while(R<0)

if (R == 0)

{

cout<<"电源短路！"<<endl

}

else{

I = U/R

cout<<"通过的电流为："<<I<<endl

}

return 0

}

不是死循环，短路程序是由于某方面的原因导致某些程序不执行，如：

a=1

1=1 or ++a=2

这段代码执行完后a值为1，因为or语句如果前面的条件为真，则后面的++a=2被短路，根本不会执行，这就是短路程序。再如：

a=1

1=2 and ++a=2

同样，and *** 作如果前面有条件为假，则表达示为假，后面的语句被短路，不会执行

---