C语言编程，求解非加权无向图（简单图）的平均路径长度

Question

请给出一个非加权无向图的求解其平均路径长度的程序,C语言.只是,非加权无向图要像以下的格式那样给出.
graph sample {
a -- b;
b -- c;
c -- a;
}

不需要纠结于什么叫非加权无向图，就是数据结构中的网状结构，无加权无向。
时间比较急，请各位大神帮帮忙
网是带权值的，上面的“网”应该是“图”，打错了
求非加权无向图的平均路径长度，C语言(像数据结构中的伪码那样就行),就这么难么...

平均路径长度：
所有点对之间的最短路径长度的算术平均值。

Answer 1

#include "stdio.h" //库包含，不用说吧
#include "math.h"
void sstf(int current,int *queue,int len)
{
int i=0,j=0,count=0,sum=0,min=0; //i记录数组位置，j用在下边的比较中,用queue[j]和当前位置current计算路径长度
//sum表示总路径长度,min用来记录步最小路径
while(1){
if(count ==len )break;
i=0;
while(queue[i]==-1){i++;} //若为-1就跳过，在下边有，是为了做到不重复

min = abs(current-queue[i]); //当前位置到数组中i位置的路径的绝对长度

for(j=i+1;j<len;j++){ //从i的下一个位置开始找出这一步的最短路径
if(queue[j]==-1)continue; //这个不用看了，若为-1就跳过，在下边有，是为了做到不重复
if(abs(current-queue[j])<min){ //用穷举比较的方法找到最短路径
min =abs(current-queue[j]);
i=j;
}//if end
} //for end

printf("%d\n",queue[i]); //屏显第i个位置
sum=sum+abs(current-queue[i]); //这一步的长度加到总长度中
current=queue[i]; //改写当前位置
queue[i]= -1; //把当前值赋为-1，下一次比较重跳过
count++;
}//while end
printf("sum=%d\n",sum); //屏显最短路径总长
printf("average=%f\n",sum*1.0/len); //屏显平均长度
}

main()
{
int current=100; //设定初始的当前位置
int queue[9]={55,58,39,18,90,160,150,38,184};//磁盘位置
sstf(current,queue,9); //调用函数计算最短路径

}

Answer 2

做出连通矩阵A，用floyd（记节点数为n）
写伪码吧……核心算法像是下面这样

D := A;

for i := 1 to n do
for j := 1 to n do
for k := 1 to n do
D[i, j] := max(D[i, j], D[i, k] + D[k, j]);

D即为所需的APSP，剩下的你懂本回答被网友采纳

Answer 3

#include <iostream.h>

void main()
{
const int m = 1000;
int matric[5][5] =
{
{0,1,m,1,m}, //graph sample { 0--1;0--3;1--2;2--3;2--4;3--4;}
{1,0,1,m,m}, //this is the adjacency matrix
{m,1,0,1,1}, //"0" means the same node to itself
{1,m,1,0,1}, //"1" means there's an edge between the two nodes
{m,m,1,1,0} //"m" means there's no edge between the two nodes
};
int patch[5][5]; //patch
int a[5][5]; //shortest record

int i,j,k,pre;

for (i=0; i<5; i++) //initialization
{
for (j=0; j<5; j++)
{
a[i][j] = matric[i][j];
patch[i][j] = j;
}
}

for (k=0; k<5; k++) //calculate the shortest
{
for (i=0; i<5; i++)
for (j=0; j<5; j++)
{
if(a[i][j] > a[i][k] + a[k][j])
{
a[i][j] = a[i][k] + a[k][j];
patch[i][j] = patch[i][k];
}
}
}

for (i=0; i<5; i++) //printing
for (j=0; j<5; j++)
{
if(a[i][j] == m)
{
cout<<"there is no patch form "<<i<<" to "<<j<<endl;
}
else
{
cout<<"the distance from "<<i<<" to "<<j<<" is "<<a[i][j];
cout<<" the patch is :"<<i;

pre = i;
do
{
pre = patch[pre][j];
cout<<"-->"<<pre;
}while (pre != j);
cout<<endl;
}
}
float total = 0, n = 0;
for (i=0; i<5; i++) //the average path length
for (j=i; j<5; j++)
{

if(a[i][j] == 0 || a[i][j] == m)
total = total;
else
{
total = total + a[i][j];
n++;
}
}
cout<<"the average path length is :"<<(total/n);
cout<<endl;
}

参考资料：I've done it myself, Thanks for your answers.

本回答被提问者采纳