是 离散数学 的题目吧
想要的话你得等等
我现在五一放假在家
程序在学校的笔记本上呢
下周一回学校
到时可以给你找找
和你的要求完全吻合（大概是完全吻合吧）
你还是留个邮箱吧
实验三 计算两结点间长度为m的路的数目
一、实验目的
熟悉邻接矩阵和两结点间长度为m的路的数目的关系并编程计算。
二、实验内容
从键盘输入图的邻接矩阵和一正整数m，计算结点两两之间长度为m的路的数目。考虑有向图和无向图。用C语言实现。
三、实验步骤
1.根据算法画出程序流程图
2.根据流程图写源程序
3.编译连接源程序得出结果
四、源程序和实验结果
源程序：
#define n 5
#include <stdio.h>
void main(void)
{
int A[n][n],An[n][n],An_1[n][n]
int i,j,k,l,m
for(i=0i<ni++)
{
for(j=0j<nj++)
scanf("%d",&A[i][j])
}
printf("\n")
scanf("%d",&m)
for(i=0i<ni++)
for(j=0j<nj++)
An_1[i][j]=A[i][j]
for(l=0l<(m-1)l++)
{
for(i=0i<ni++)
for(j=0j<nj++)
for(k=0k<nk++)
{
if(k==0)An[i][j]=An_1[i][k]*A[k][j]
else An[i][j]=An[i][j]+(An_1[i][k]*A[k][j])
}
for(i=0i<ni++)
for(j=0j<nj++)
An_1[i][j]=An[i][j]
}
printf("An\n")
for(i=0i<ni++)
{
for(j=0j<nj++)
printf("%d ",An[i][j])
printf("\n")
}
}
实验结果：
0 1 0 0 0
1 0 1 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 1 0
4
An
2 0 2 0 0
0 4 0 0 0
2 0 2 0 0
0 0 0 1 0
0 0 0 0 1
Press any key to continue
不好意思 错了 没权值矩阵 不好意思
分给上边的那位吧
不好意思 又找到了 东西有点乱。。。。
#define n 5
#include <stdio.h>
void main(void)
{
int bijiao(int a,int b,int c[n])
int linjie[n][n]={0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0}//邻接矩阵
int quanzhi[n][n]={0,1,0,3,2,1,0,2,2,1,0,2,0,2,0,3,2,2,0,3,2,1,0,3,0}//权值矩阵
int yi[n]={100,100,100,100,100},shengchengshu[n][n],shengchengshu2[n][n]
int i,j,k,temp1,temp2,temp3,he=0,buchonghe
for(i=0i<ni++)
for(j=0j<nj++)
shengchengshu[i][j]=0
temp1=100
for(i=0i<ni++)
for(j=ij<nj++)
if((quanzhi[i][j]<temp1)&&(quanzhi[i][j]!=0))
{
temp1=quanzhi[i][j]
yi[0]=i
yi[1]=j
}
shengchengshu[yi[0]][yi[1]]=1
printf("temp1=%d\n",temp1)
he=he+temp1
for(k=0k<(n-2)k++)
{
temp2=100
for(i=0i<(k+2)i++)
for(j=0j<nj++)
if(linjie[yi[i]][j]==1)
if(buchonghe=bijiao(k,j,yi))
if((quanzhi[yi[i]][j]<temp2)&&(quanzhi[yi[i]][j]!=0))
{
temp2=quanzhi[yi[i]][j]
yi[k+2]=j
temp3=yi[i]
}
printf("temp2=%d\n",temp2)
shengchengshu[temp3][yi[k+2]]=1
he=he+temp2
}
for(i=0i<ni++)
for(j=0j<nj++)
shengchengshu2[j][i]=shengchengshu[i][j]
for(i=0i<ni++)
for(j=0j<nj++)
shengchengshu[i][j]=shengchengshu[i][j]||shengchengshu2[i][j]
printf("he=%d\n",he)
for(i=0i<ni++)
printf("%d",yi[i])
printf("\n")
for(i=0i<ni++)
{
for(j=0j<nj++)
printf("%d ",shengchengshu[i][j])
printf("\n")
}
}
int bijiao(int k,int j,int yi[n])
{
int i
int buchonghe
for(i=0i<(k+2)i++)
{
if(i==0)buchonghe=(j!=yi[i])
else buchonghe=(buchonghe&&(j!=yi[i]))
}
return buchonghe
}
和你的要求一模一样 用C语言实现的 就是当时为了调试没有输入
你自己把那两个矩阵改成输入就可以了
基本上所有变量都是用汉语拼音的 你应该可以看懂
我相信你的智商 嘿嘿 给分吧
最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：
常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。
Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决著名的旅行商问题。
问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。
为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。
以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：
注：
01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3
第1步 ：选取顶点 添加进
第2步 ：选取顶点 添加进 ，更新 中顶点最短距离
第3步 ：选取顶点 添加进 ，更新 中顶点最短距离
第4步 ：选取顶点 添加进 ，更新 中顶点最短距离
第5步 ：选取顶点 添加进 ，更新 中顶点最短距离
第6步 ：选取顶点 添加进 ，更新 中顶点最短距离
第7步 ：选取顶点 添加进 ，更新 中顶点最短距离
示例：node编号1-7分别代表A,B,C,D,E,F,G
(s.paths <- shortest.paths(g, algorithm = "dijkstra"))输出结果：
(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))输出结果：
示例：
找到D（4）到G（7）的最短路径：
[1] 维基百科，最短路径问题： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths
[5]Pypi: https://pypi.org/project/Dijkstar/
你想输出路径吗？记录一下每个点的直接前驱，然后反向查找
#include <stdio.h>
const int maxdot=100
int dist[maxdot]
int previous[maxdot] //record the directly previous node
void ShortPaths(int v,int c[maxdot][maxdot],int n)
{
int i,jbool s[maxdot]
int p[maxdot][maxdot]
for(i=1i<=ni++)
{
dist[i]=c[v][i]
previous[i]=v
s[i]=false
}
dist[v]=0s[v]=true
for(i=1i<ni++)
{
int temp=10000
int u=v
for(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]<1000))
{
int newdist=dist[u]+c[u][j]
if(newdist<dist[j])
{
dist[j]=newdist
previous[j]=u //update the directly previous node
}
}
}
}
}
void find(int v,int u) // 'v' here must be identical with the 'v' in above function
{
//output the path in reverse order
while(u!=previous[u])
{
u=previous[u] // retrieve the previous node
printf("%d\n",u)
}
}
