離散數學作業請描述一下最短路徑是什麼

① 如何用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語言實現的 就是當時為了調試沒有輸入
你自己把那兩個矩陣改成輸入就可以了
基本上所有變數都是用漢語拼音的 你應該可以看懂
我相信你的智商 嘿嘿 給分吧