#define n 9
#define I=99999
main()
{
int G[n+1][n+1]
int D[n+1][n+1]
int P[n+1][n+1]
int i,j,k
FILE *fp
if((fp=fopen("d:2.c","r"))==NULL)
{printf("cannot open the file1\n")
exit(0)
}
for(i=1i<=ni++)
for(j=1j<=nj++)
fscanf(fp,"%d",&G[i][j])
fclose(fp)
if(ferror(fp)!=0)
printf("close the file error2\n")
for(i=1i<=ni++)
for(j=1j<=nj++)
{
D[i][j]=G[i][j]
P[i][j]=i
}
for(i=1i<=ni++)
{
D[i][i]=0
P[i][i]=0
}
for(k=1k<=nk++)
for(i=1i<=ni++)
for(j=1j<=nj++)
if(D[i][j]>D[i][k]+D[k][j])
{
D[i][j]=D[i][k]+D[k][j]
P[i][j]=P[k][j]
}
for(i=1i<=ni++)
for(j=1j<=nj++)
{
if(i==j) break
else
{
printf("%d to %d de zuiduanlujing wei:\n",i,j)
while(1)
{
if(j!=i)
{
printf("%d-->",j)
j=P[i][j]
}
else
{
printf("%d",i)
break
}
}
}
}
}
************************************
其中数据文件中的数据为：
0 3 I 3 I I I I I
3 0 3 I 2 I I I I
I 3 0 I I 4 I I I
3 I I 0 3 I 3 I I
I 2 I 3 0 I I 3 I
I I 4 I 2 0 I I 5
I I I 3 I I 0 4 I
I I I I 3 I 4 0 2
I I I I I 5 I 2 0
///////////////////////////////////////////////////////////////////////
for(i=1i<=ni++)
{
for(j=1j<=nj++)
｛fscanf(fp,"%d",&G[i][j])
printf("%d ",G[i][j])
｝
printf("\n")
} 查一下G数组的内容
上面是dijkstra算法，效率比较低，你可以采用Floyd算法：
下面是主要代码：
Public Function Floyd()
Dim i As Long, j As Long, k As Long
'初始化
For i = 1 To N
For j = 1 To N
D(i, j) = A(i, j)
Next j
Next i
For i = 1 To N
For j = 1 To N
P(i, j) = 0
Next j
Next i
For i = 1 To N
For j = 1 To N
If D(i, j) <INF Then 'J是I的后继点
P(i, j) = j
End If
Next j
Next i
'迭代N次,复杂度为N的三次方 算法的核心！！！！！！！！
For k = 1 To N
For i = 1 To N
For j = 1 To N
If D(i, k) + D(k, j) <D(i, j) Then
D(i, j) = D(i, k) + D(k, j)
P(i, j) = P(i, k)
End If
Next j
Next i
Next k
End Function
Dijkstra算法
实验目的：
给定一个（无向）图G，及G中的两点s、t，确定一条从s到t的最短路径。
实验要求：
输入图G的顶点数n。接下来的n行描述这一个图形，采用邻接表方式，其中的第i行有n个数，依次表示第i个顶点与第1、2、3、…、n个顶点的路径长。假如两个顶点间无边相连，用一个大数maxint（如65535）表示。再在下面的一行上给出两个整数i、j表示要求最短距离的两个顶点i和顶点j。
输出两个顶点i和顶点j的最短距离，同时给出最短路径上的顶点序列。
注意：每行上的两个相邻数间用一个空格隔开。
实验结果：
输入
4
0 2 65535 4
2 0 3 65535
65535 3 0 2
4 65535 2 0
1 3
输出
The least distance from l to 3 is 5.
The path is 1->2->3
程序代码：
#include<iostream>
using namespace std
void Dijkstra(int n,int v,int dist[],int prev[],int **c)
{
int maxint=65535
bool *s=new bool[n]
for(int i=1i<=ni++)
{
dist[i]=c[v][i]
s[i]=false
if(dist[i]==maxint)prev[i]=0
else prev[i]=v
}
dist[v]=0
s[v]=true
for(i=1i<ni++)
{
int temp=maxint
int u=v
for(int j=1j<=nj++)
if((!s[j])&&(dist[j]<temp))
{
u=j
temp=dist[j]
}
s[u]=true
for(j=1j<=nj++)
if((!s[j])&&(c[u][j]<n))
{
int newdist=dist[u]+c[u][j]
if(newdist<dist[j])
{
dist[j]=newdist
prev[j]=u
}
}
}
}
void main()
{
int n,v,u
int q=0
cin>>n
int *way=new int[n+1]
int **c=new int *[n+1]
for(int i=1i<=ni++)
{
c[i]=new int[n+1]
}
for(int j=1j<=nj++)
for(int t=1t<=nt++)
cin>>c[j][t]
int *dist=new int [n]
int *prev=new int [n]
cin>>v>>u
Dijkstra(n,v,dist,prev,c)
cout<<"最短路径从"<<v<<" ->"<<u<<" 的距离是 "<<dist[u]<<endl
int w=u
while(w!=v)
{
q++
way[q]=prev[w]
w=prev[w]
}
for(j=qj>=1j--)
{
cout<<way[j]<<" ->"
}
cout<<u<<endl
}
程序分析：
a[i][j]记边（i,j）的权，数组dist[u]记从源v到顶点u所对应的最短特殊路径长度
算法描述如下：
S1:初始化，S, T,对每个yS，{dist[y]=a[v][y],prev[y]=nil}
S2:若S=V，则输出dist,prev,结束
S3：uV\S中有最小dist值的点，SS{u}
S4：对u的每个相邻顶点x，调整dist[x]：即
若dist[x]>dist[u]+a[u][x],则{dist[x]=dist[u]+a[u][x]，prev[x]=u},转S2
对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。算法的其余部分所需要时间不超过O(n2)。
实验体会：
这个是经典贪谈心选择算法，与图论的结合更加加深了它的思维深度。画出一个表格之后，才得以理解。然后用书上的结构试验了一下，发觉一开始没有成功。是因为书上的有几个错误，在maxint等上面。修改好后，创建了一个2维动态数组，之后非常顺利。
用邻接矩阵表示的图的Dijkstra算法的源程序*/
#include<stdio.h>
#define MAXVEX 100
typedef char VexType
typedef float AdjType
typedef struct
{ VexType vexs[MAXVEX]/* 顶点信息 */
AdjType arcs[MAXVEX][MAXVEX]/* 边信息 */
int n/* 图的顶点个数 */
}GraphMatrix
GraphMatrix graph
typedef struct {
VexType vertex/* 顶点信息 */
AdjType length/* 最短路径长度 */
int prevex/* 从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点 */
}Path
Path dist[6]/* n为图中顶点个数*/
#define MAX 1e+8
void init(GraphMatrix* pgraph, Path dist[])
{
int idist[0].length=0dist[0].prevex=0
dist[0].vertex=pgraph->vexs[0]
pgraph->arcs[0][0]=1/* 表示顶点v0在集合U中 */
for(i=1i<pgraph->ni++) /* 初始化集合V-U中顶点的距离值 */
{ dist[i].length=pgraph->arcs[0][i]
dist[i].vertex=pgraph->vexs[i]
if(dist[i].length!=MAX)
dist[i].prevex=0
else dist[i].prevex= -1
}
}
void dijkstra(GraphMatrix graph, Path dist[])
{ int i,j,minvexAdjType min
init(&graph,dist)/* 初始化，此时集合U中只有顶点v0*/
for(i=1i<graph.ni++)
{ min=MAXminvex=0
for(j=1j<graph.nj++)
if( (graph.arcs[j][j]==0) &&(dist[j].length<min) ) /*在V-U中选出距离值最小顶点*/
{ min=dist[j].lengthminvex=j}
if(minvex==0) break/* 从v0没有路径可以通往集合V-U中的顶点 */
graph.arcs[minvex][minvex]=1/* 集合V-U中路径最小的顶点为minvex */
for(j=1j<graph.nj++) /* 调整集合V-U中的顶点的最短路径 */
{ if(graph.arcs[j][j]==1) continue
if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j])
{ dist[j].length=dist[minvex].length+graph.arcs[minvex][j]
dist[j].prevex=minvex
}
}
}
}
void initgraph()
{
int i,j
graph.n=6
for(i=0i<graph.ni++)
for(j=0j<graph.nj++)
graph.arcs[i][j]=(i==j?0:MAX)
graph.arcs[0][1]=50
graph.arcs[0][2]=10
graph.arcs[1][2]=15
graph.arcs[1][4]=5
graph.arcs[2][0]=20
graph.arcs[2][3]=15
graph.arcs[3][1]=20
graph.arcs[3][4]=35
graph.arcs[4][3]=30
graph.arcs[5][3]=3
graph.arcs[0][4]=45
}
int main()
{
int i
initgraph()
dijkstra(graph,dist)
for(i=0i<graph.ni++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex)
return 0
}
请指教“单源最短路径”问题
看一下我的程序怎么运行得不到正确的结果啊？次程序实现的功能是求单源最短路径，高手请帮忙~！~！~！感激感激
#define N 6 //顶点数
#define MAX 1000//max是计算机允许的最大值
void main()
{int cost[N][N] //cost为带权有向图的邻接矩阵
int v=0
int a,b
int dist[N],s[N],rear[N] //dist[i]为当前源点到顶点i的最小距离,s表示相应顶点是否并入集合的标志//到i顶点的最短路径存储在队列q[i]中,队头指针为0,队尾指针存储在节rear[i]中
int q[N][N]
int i,j,k,win,m
for(a=0a<=5a++)
for(b=0b<6b++)
scanf("%d",&cost[a][b])
for (i=1i<Ni++) //初始化s和rear
{ s[i]=0
rear[i]=-1
}
for (i=1i<Ni++) //初始化dist和q
{ dist[i]=cost[v][i]
if (dist[i]<MAX)
{q[i][++rear[i]]=v
q[i][++rear[i]]=i
}
}
s[v]=1 //v并入集合
for (k=0k<N-1k++)//并入n-1个顶点,即求n-1条最短路径
{ win=MAXj=v
for (i=1i<Ni++) //选最小的dist[j]
if (s[i]==0&&dist[i]<win)
{ j=iwin=dist[i]}
if (j!=i)
{ s[j]=1
printf("\nthe %d's shortestdistance is %d\n",j,dist[j])
for (i=0i<=rear[j]i++)
printf("%5d",q[j][i]) //打印从源点到j的最短路径
for (i=1i<Ni++)
if (s[i]==0&&((dist[j]+cost[j][i])<dist[i])) //现在从源点经过j到i比原来要短则修改
{ dist[i]=dist[j]+cost[j][i]
for (m=0m<=rear[j]m++)
q[i][m]=q[j][m] //修改相应的路径
rear[i]=rear[j]
q[i][++rear[i]]=i
}
}
}
}
（2）算法基本思想
设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。
①初始化
初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s}，蓝点集为空。
②重复以下工作，按路径长度递增次序产生各顶点最短路径
在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。
当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
注意：
①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。
（3）在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
源点，红点1，红点2，…，红点n，蓝点k
距离为：源点到红点n最短距离+<红点n,蓝点k>边长
为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈ V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度（简称估计距离）。
若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V-S}，则D[k]=SD(k)。
初始时，每个蓝点v的D[c]值应为权w<s，v>，且从s到v的路径上没有中间点，因为该路径仅含一条边<s，v>。
注意：
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
（4）k扩充红点集s后，蓝点集估计距离的修改
将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。
对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=<s，…，k，j>。且D[j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。
所以，当length(P)=D[k]+w<k，j>小于D[j]时，应该用P的长度来修改D[j]的值。
（5）Dijkstra算法
Dijkstra(G，D，s){
//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化 *** 作
S={s}；D[s]=0； //设置初始的红点集及最短距离
for( all i∈ V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]； //设置i初始的估计距离为w<s，i>
//以下是扩充红点集
for(i=0i<n-1i++)do{//最多扩充n-1个蓝点到红点集
D[k]=min{D[i]：all i V-S}； //在当前蓝点集中选估计距离最小的顶点k
if(D[k]等于∞)
return； //蓝点集中所有蓝点的估计距离均为∞时，
//表示这些顶点的最短路径不存在。
S=S∪{k}； //将蓝点k涂红后扩充到红点集
for( all j∈V-S )do //调整剩余蓝点的估计距离
if(D[j]>D[k]+G[k][j])
//新红点k使原D[j]值变小时，用新路径的长度修改D[j]，
//使j离s更近。
D[j]=D[k]+G[k][j]；
}
}
【例】对有向网G8以0为源点执行上述算法的过程及红点集、k和D向量的变化见【参见动画演示】。
（6）保存最短路径的Dijkstra算法
设置记录顶点双亲的向量P[0．．n-1]保存最短路径：
当顶点i无双亲时，令P[i]=-1。
当算法结束时，可从任一P[i]反复上溯至根(源点)求得顶点i的最短路径，只不过路径方向正好与从s到i的路径相反。
具体的求精算法【参见教材】 。
Dijkstra算法的时间复杂度为O(n2)
其他最短路径问题
最短路径问题的提法很多，其它的最短路径问题均可用单源最短路径算法予以解决：
①单目标最短路径问题(Single-Destination Shortest-Paths Problem)：找出图中每一顶点v到某指定顶点u的最短路径。只需将图中每条边反向，就可将这一问题变为单源最短路径问题，单目标u变为单源点u。
②单顶点对间最短路径问题(Single-Pair Shortest-Path Problem)：对于某对顶点u和v，找出从u到v的一条最短路径。显然，若解决了以u为源点的单源最短路径问题，则上述问题亦迎刃而解。而且从数量级来说，两问题的时间复杂度相同。
③所有顶点对间最短路径问题(All-Pairs Shortest-Paths Problem)：对图中每对顶点u和v，找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题算法予以解决。
/*************************************************************** 给定一个带权有向图G = (V，E)，其中每条边的权是一个非负整数。*
* 另外还给定V中的一个顶点，称为源。现在我们要计算从源到所有其 *
* 他各顶点的最短路长度。这里路径长度是路上各边权之和。这个问 *
* 题通常称为单源最短路径问题。 *
***************************************************************/
#include<iostream.h>
#define INFINITE 100
void main()
{
int j,i,n,k,t,**w,*s,*p,*d
cout<<"input the value of n:"
cin>>n
cout<<endl
d = new int[n]
s = new int[n]
p = new int[n]
w = new int*[n]
for(i = 0i <ni++)
{
w[i] = new int[n]
}
for(i = 0i <ni++)
for(j = 0j <nj++)
cin>>w[i][j]
for(s[0] = 1,i = 1i <ni++)
{
s[i] = 0
d[i] = w[0][i]
if(d[i] <INFINITE)
p[i]=0
else
p[i]=-1
}
for(i = 1i <ni++)
{
t = INFINITE
k = 1
for(j = 1j <nj++)
if((!s[j]) &&(d[j] <t))
{
t = d[j]
k = j
}
s[k]=1//point k join the S
for (j = 1j <nj++)
if((!s[j]) &&(d[j] >d[k] + w[k][j]))
{
d[j] = d[k] + w[k][j]
p[j] = k
}
}
cout<<"从源点到其它顶点的最短距离依次如下："
for(i=1i<ni++) cout<<d[i]<<" "
cout<<endl
}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/
c语言实现网络，我想你是说用VC开放win32的应用程序吧，直接用API函数，不是c语言实现！它既具有高级语言的特点，又具有汇编语言的特点。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。
1.一个C语言源程序可以由一个或多个源文件组成。 2.每个源文件可由一个或多个函数组成。 3.一个源程序不论由多少个文件组成，都有一个且只能有一个main函数，即主函数。 4.源程序中可以有预处理命令(include 命令仅为其中的一种)，预处理命令通常应放在源文件或源程序的最前面。 5.每一个说明，每一个语句都必须以分号结尾。但预处理命令，函数头和花括号“}”之后不能加分号。 6.标识符，关键字之间必须至少加一个空格以示间隔。若已有明显的间隔符，也可不再加空格来间隔。
底下是重点了，C语言不是万能的
1. C语言的缺点主要表现在数据的封装性上，这一点使得C在数据的安全性上有很大缺陷，这也是C和C++的一大区别。 2. C语言的语法限制不太严格，对变量的类型约束不严格，影响程序的安全性，对数组下标越界不作检查等。从应用的角度，C语言比其他高级语言较难掌握。 [C语言指针] 指针是C语言的一大特色，可以说是C语言优于其它高级语言的一个重要原因。就是因为它有指针，可以直接进行靠近硬件的 *** 作，但是C的指针 *** 作也给它带来了很多不安全的因素。C++在这方面做了很好的改进，在保留了指针 *** 作的同时又增强了安全性。Java取消了指针 *** 作，提高了安全性，适合初学者使用。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）