离散数学作业请描述一下最短路径是什么

① 如何用C语言来求最短路径

使用发散的方法，从起点开始，一次增加一个接点，也就是增加一个路径，直到，目的接点出现，那么你做了几次发散，路径就是几，而且它就是最短路径。

如果不对，请把题目说的详细一点，尤其是哪个概率。

② 离散数学中的最短路问题怎么求

从下往上，用贪婪算法

③ 离散数学，135题求速度，过了给红包

第1题

(¬P→Q)→¬R

⇔ ¬(¬P→Q)∨¬R 变成 合取析取

⇔ ¬(P∨Q)∨¬R 变成 合取析取

⇔ (¬P∧¬Q)∨¬R 德摩根定律

⇔(¬P∨¬R)∧(¬Q∨¬R)分配律

⇔ (¬P∨(¬Q∧Q)∨¬R)∧((¬P∧P)∨¬Q∨¬R) 补项

⇔ ((¬P∨¬Q∨¬R)∧(¬P∨Q∨¬R))∧((¬P∧P)∨¬Q∨¬R) 分配律

⇔ (¬P∨¬Q∨¬R)∧(¬P∨Q∨¬R)∧((¬P∧P)∨¬Q∨¬R) 结合律

⇔ (¬P∨¬Q∨¬R)∧(¬P∨Q∨¬R)∧((¬P∨¬Q∨¬R)∧(P∨¬Q∨¬R)) 分配律

⇔ (¬P∨¬Q∨¬R)∧(¬P∨Q∨¬R)∧(¬P∨¬Q∨¬R)∧(P∨¬Q∨¬R) 结合律

⇔ (¬P∨Q∨¬R)∧(¬P∨¬Q∨¬R)∧(P∨¬Q∨¬R) 等幂律

得到主合取范式，再检查遗漏的极大项

⇔ M₃∧M₅∧M₇
⇔ ∏(3,5,7)
⇔ ¬∏(0,1,2,4,6)
⇔ ∑(0,1,2,4,6)
⇔ m₀∨m₁∨m₂∨m₄∨m₆

⇔ ¬(P∨Q∨R)∨¬(P∨Q∨¬R)∨¬(P∨¬Q∨R)∨¬(¬P∨Q∨R)∨¬(¬P∨¬Q∨R) 德摩根定律

⇔ (¬P∧¬Q∧¬R)∨(¬P∧¬Q∧R)∨(¬P∧Q∧¬R)∨(P∧¬Q∧¬R)∨(P∧Q∧¬R) 德摩根定律

得到主析取范式

第3题

dijkstra算法（如图所示）

从总部（1）出发，可到达（2）（3），

权重分别为15,10，选出最小的权重10【到达（3）】，

得到路径（1）（3）

此时

（1）到（3）的最短路径是10

（1）到（2）的最短路径是15

从（3）出发，可到达（2）（5），

权重分别为3,4，选出最小的权重3，得到路径

（1）（3）（2）

此时

（1）到（3）的最短路径是10

（1）到（2）的最短路径是10+3=13

（1）到（5）的最短路径是10+4=14

从（2）出发，可到达（4）（7），

权重分别为6,17，选出最小的权重6，得到路径

（1）（3）（2）（4）

此时

（1）到（3）的最短路径是10

（1）到（2）的最短路径是10+3=13

（1）到（4）的最短路径是10+3+6=19

（1）到（5）的最短路径是10+4=14

从（4）出发，可到达（5）（7），

权重分别为4,5，选出最小的权重4，得到路径

（1）（3）（2）（4）（5）

此时

（1）到（3）的最短路径是10

（1）到（2）的最短路径是10+3=13

（1）到（4）的最短路径是10+3+6=19

（1）到（5）的最短路径是10+4=14

（1）到（7）的最短路径是10+3+6+5=24

从（5）出发，可到达（6），

权重为2，得到路径

（1）（3）（2）（4）（5）（6）

此时

（1）到（3）的最短路径是10

（1）到（2）的最短路径是10+3=13

（1）到（4）的最短路径是10+3+6=19

（1）到（5）的最短路径是10+4=14

（1）到（7）的最短路径是10+3+6+5=24

（1）到（6）的最短路径是10+4+2=16

从（6）出发，可到达（7），

权重为6，得到路径

（1）（3）（2）（4）（5）（6）（7）

此时

（1）到（3）的最短路径是10

（1）到（2）的最短路径是10+3=13

（1）到（4）的最短路径是10+3+6=19

（1）到（5）的最短路径是10+4=14

（1）到（7）的最短路径是10+4+2+6=22

（1）到（6）的最短路径是10+4+2=16

至此已经找到全部最短路径。

④ 离散数学标号法求最短路径怎么求，书上写的看不懂，谁能用通俗的语言让我明白……举例子可以用下图。可以

做了很久的ppt，望采纳~~~~~~~~~~~~~~~~

⑤ 离散数学最短路径的问题 带权图

从v0开始

可以发现有v1,v2两个顶点相连
计算权重，选权重小的那条边v0v1。
然后从v1，开始观察与v1相连的点v3,v2,v4
v1、v3相连的路径，权重最小的是v1v2v4v3=6，舍去v1v3这条边
v1、v4相连的路径，权重最小的是v1v2v4=2+1=3，舍去v1v4这条边
v1、v2相连的路径，权重最小的是v1v2=2

v4、v5相连的路径，权重最小的是v4v3v5=3+2=5，舍去v4v5这条边

⑥ 在复习离散数学的时候，复习到图论，发现那几个最短路径，最小生成树的算法，原理其实很好理解，但是翻一

编程能力都是一行一行代码积累出来的，当你有1k行编程经验的时候，你的编程算入门，当你有1w行编程经验的时候，你的编程算熟练，当你有5w+行以上的编程经验时，你的编程算精通。把书上的例子嗷嗷的拿出来编，然后什么都明白了。

⑦ 离散数学最短路径问题，想知道那个图的LF那一行是怎么得来的应该很简单，急求啊

这不是最短路径问题，是关键路径问题。

我们把从源点到汇点的最长路径(路径上各边的权值之和)称为关键路径

事件的最早发生时间E(vi) 和最迟发生时间 L(vj)
E(vi)：从源点v1到vi的最长路径的长度
L(vi)：在不推迟整个工程完成的前提下，一个事件vi允许的最迟发生时间。
L(vi)=E(vn)－vi到vn的最长路径的长度

活动的最早开工时间 ES(ai)
最迟开工时间 LS(aj)
最早完工时间 EE(ai)
最迟完工时间 LE(aj)
最迟开工时间和最迟完工时间，均是在不推迟整个工程完成的前提下

计算方法：
①E(vj)的计算：从源点开始，自左到右对每个事件向前计算，直至计算到汇点为止。可用如下递推公
式：
E(v1)=0
E(vj)=max{E(vi)+w(i,j)} (j = 2,…,n)
②L(vj)的计算：从汇点开始，自右到左逐个事件逆推计算，直至计算到源点为止。可用如下递推公式：
L(vn)=E(vn)
L(vj)=min{L(vk)－w(j,k)} (j = n-1,…1)
若活动ai由边<vj,vk>表示，则有：
ai的最早开工时间： ES(ai) = E(vj)
ai的最迟开工时间： LS(ai) = L(vk)－w(j,k)
ai的最早完工时间： EE(ai) = E(vj) ＋w(j,k)
ai的最迟完工时间： LE(ai) = L(vk)

如果你认可我的回答，敬请及时采纳，
祝你学习进步，更上一层楼！ (*^__^*)

⑧ 关于离散数学中的Floyd-Warshall算法求两个节点间的最短路径问题

在离散数学中用的warshall算法，应该是用来求传递闭包的吧。
你如果想解决最短路径问题，可以参考专门讲算法的书（如：《算法概论》），可以用Warshall算法，动态规划，分支定界等等很多算法解决这个问题。

⑨ 离散数学中用迪克斯特拉算法求出a到z的最短路径，详细的解答过程

离散数学中用迪克斯特拉算法求出a到z的最短路径，详细的解答过程

最短距离是8，不过你图中没有中间结点的标号，不好说明哦

离散数学中用迪克斯特拉算法求出a到z的最短路径，详细的解答过程

⑩ 最短路径 程序

上学期曾经编过
是 离散数学 的题目吧
想要的话你得等等
我现在五一放假在家
程序在学校的笔记本上呢
下周一回学校
到时可以给你找找
和你的要求完全吻合（大概是完全吻合吧）
你还是留个邮箱吧

实验三 计算两结点间长度为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=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&A[i][j]);
}
printf("\n");
scanf("%d",&m);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
An_1[i][j]=A[i][j];
for(l=0;l<(m-1);l++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
{
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=0;i<n;i++)
for(j=0;j<n;j++)
An_1[i][j]=An[i][j];
}
printf("An\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
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 quan[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=0;i<n;i++)
for(j=0;j<n;j++)
shengchengshu[i][j]=0;
temp1=100;
for(i=0;i<n;i++)
for(j=i;j<n;j++)
if((quan[i][j]<temp1)&&(quan[i][j]!=0))
{
temp1=quan[i][j];
yi[0]=i;
yi[1]=j;
}
shengchengshu[yi[0]][yi[1]]=1;
printf("temp1=%d\n",temp1);
he=he+temp1;
for(k=0;k<(n-2);k++)
{
temp2=100;
for(i=0;i<(k+2);i++)
for(j=0;j<n;j++)
if(linjie[yi[i]][j]==1)
if(buchonghe=bijiao(k,j,yi))
if((quan[yi[i]][j]<temp2)&&(quan[yi[i]][j]!=0))
{
temp2=quan[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=0;i<n;i++)
for(j=0;j<n;j++)
shengchengshu2[j][i]=shengchengshu[i][j];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
shengchengshu[i][j]=shengchengshu[i][j]||shengchengshu2[i][j];
printf("he=%d\n",he);
for(i=0;i<n;i++)
printf("%d",yi[i]);
printf("\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d ",shengchengshu[i][j]);
printf("\n");
}
}
int bijiao(int k,int j,int yi[n])
{
int i;
int buchonghe;
for(i=0;i<(k+2);i++)
{
if(i==0)buchonghe=(j!=yi[i]);
else buchonghe=(buchonghe&&(j!=yi[i]));
}
return buchonghe;
}
和你的要求一模一样 用C语言实现的 就是当时为了调试没有输入
你自己把那两个矩阵改成输入就可以了
基本上所有变量都是用汉语拼音的 你应该可以看懂
我相信你的智商 嘿嘿 给分吧