南京工程學院
通訊工程學院
課程設計說明書(**)
題目最小代價演算法
課程名稱計算機通訊與網路b
專業通訊工程學院
班級學生姓名
學號設計地點
指導教師
設計起止時間：2015 年6 月 8日至2015 年 6月12 日
目錄一．實驗目的3
二．實驗要求3
三．具體流程4
3.1.1dijkstra演算法分析4
3.1.2dijkstra演算法流程圖5
3.1.3執行結果截圖6
3.2.1bellman演算法分析7
3.2.2bellman演算法流程圖7
3.2.3執行結果截圖7
四． 課程設計總結8
五．源程式**8
六．參考文獻14
一． 實驗目的：
在學習《計算機通訊與網路》課程的基礎上，進一步深入理解計算機網路的體系結構、
各層主要功能和相關應用技術，提高tcp/ip網路的應用和設計能力；按照教學計畫的
要求，利用一周時間，綜合應用所學知識，設計具有一定功能的網路小軟體，培養學
生一定的自學能力和獨立分析問題、解決問題的能力，要求學生能通過獨立思考、查
閱工具書、參考文獻，提出自己的設計方案，找出設計中遇到問題的解決途徑。
完成路由演算法中的最小代價演算法：dijkstra和bellman兩個演算法。
二． 實驗要求：
（1）螢幕輸入結點個數、結點之間的鏈路及其代價，編寫程式，完成任意2個結點之間的最小代價的計算；
（2）基本任務為必做專案，附加任務為選做專案；
（3）對課程設計進行總結，撰寫課程設計報告。課程設計報告內容主要包括設計目的、設計要求、程式設計流程圖和執行結果，可手寫或列印。
設計任務：
1． 基本任務：單向鏈路。
鏈路代價2個方向都是相同的，計算最小代價。
2． 附加任務：雙向鏈路。
鏈路代價2個方向不相同，計算最小代價。
工作量要求：
1． 設計的程式流程圖；
2． c語言程式**；
3． 系統執行結果符合課程設計要求。
三． 具體流程：
3.1.1dijkstra演算法分析
需求和規格說明：
dijkstra演算法是典型最短路演算法，用於計算乙個節點到其他所有節點
的最短路徑。主要特點是以起始點為中心向外層層擴充套件，直到擴充套件到
終點為止。dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計
算的節點很多，所以效率低。
演算法本身並不是按照我們的思維習慣——求解從原點到第乙個點最
短路徑，再到第二個點的最短路徑，直至最後求解完成到第n個點的
最短路徑，而是求解從原點出發的各有向路徑的從小到大的排列但是
演算法最終確實得到了從原點到圖中其餘各點的最短路徑，可以說這是
個副產品，對於演算法的終結條件也應該以求得了原點到圖中其餘各點
的最短路徑為宜。
dijkstra演算法是用來求任意兩個頂點之間的最短路徑。在該實驗中，
我們用鄰接矩陣來儲存圖。在該程式中設定乙個二維陣列來儲存任兩
個頂點之間的邊的權值。然後通過最短路徑的計算，輸入從任意兩個
頂點之間的最短路徑的大小。
3.1.2dijkstra演算法流程圖
3.1.3執行結果截圖
3.2.1bellman演算法分析
bellman-ford演算法是求含負權圖的單源最短路徑演算法，效率很低，但**很容易寫。即進行持續地鬆弛（原文是這麼寫的，為什麼要叫鬆弛，爭議很大），每次鬆弛把每條邊都更新一下，若n-1次鬆弛後還能更新，則說明圖中有負環，無法得出結果，否則就成功完成。bellman-ford演算法有乙個小優化：
每次鬆弛先設乙個標識flag，初值為false，若有邊更新則賦值為true，最終如果還是false則直接成功退出。
演算法描述：
1.初始化：將除源點外的所有頂點的最短距離估計值 d[v] ←+∞, d[s] ←0;
2.迭代求解：反覆對邊集e中的每條邊進行鬆弛操作，使得頂點集v中的每個頂點v的最短距離估計值逐步逼近其最短距離；（執行|v|-1次）
3.檢驗負權迴路：判斷邊集e中的每一條邊的兩個端點是否收斂。
如果存在未收斂的頂點，則演算法返回false，表明問題無解；否則演算法返回true，並且從源點可達的頂點v的最短距離儲存在 d[v]中。
適用範圍或條件：
1.單源最短路徑(從源點s到其它所有頂點v);
2.有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬於邊集e的有向圖);
3.邊權可正可負(如有負權迴路輸出錯誤提示);
4.差分約束系統;
3.2.2bellman演算法流程圖
3.2.3執行結果截圖
四． 課程設計總結
本次課程設計讓我對dijkstra和bellman演算法有了一定的了解，兩者都解決了最小代價這一演算法，有各自的特色也有不足之處。dijkstra演算法就是比較耗路徑，用選代方法效率高些。相對來說bellman演算法效率就頗為低些，迭代方法耗時的同時還要判斷負權迴路，但它操作更具體明了。
設計過程中不僅鍛鍊了自己修改程式的能力，更多是加強了對程式的思維，在與同學的交流合作中也鍛鍊到了自己。
五． 源程式**
dijkstra演算法程式**：
#include<>
#include<>
//dijkstra演算法實現函式
void dijkstra(int n,int v,int dist,int prev,int **cost)
else
}dist[v] = 0;
s[v] = 1;//源節點作為最初的s子集
for (i = 1; i < n; i++)
s[u] = 1;
計算加入新的節點後，更新路徑使得其產生代價最短
for (j = 1; j <= n; j++)
}}//展示最佳路徑函式
void showpath(int n,int v,int u,int *dist,int *prev)
//輸出路徑
printf("the best path is:\n");
for (j = count; j >= 1; j--)
printf("%d\n",u);
}//主函式，主要做輸入輸出工作
void main()
{ int i,j,t;
int n,v,u;
int **cost;//代價矩陣
int *dist;//最短路徑代價
通訊錄管理系統C語言課設
瀋陽工程學院 程式設計基礎 課程設計 設計題目 通訊錄管理系統 院別資訊學院班級 學生姓名 xx 學號 2012417105 2012417103 2012417102 指導教師 職稱副教授講師 起止日期 2013年5月27日起 至 2013年6月7日止 瀋陽工程學院 課程設計任務書 課程設計題目 ...
設施規劃與物流分析課設案例
目錄一 概述2 二 基本要素分析2 2.1柴油機機油幫浦結構及有關引數2 2.2作業單位劃分3 2.3柴油機機油幫浦生產工藝過程3 三 物流分析9 3.1產品工藝過程分析10 3.2 物流強度等級的劃分11 四 作業單位非物流相關分析14 4.1整理主因，給出理由編碼13 4.2 確定相互關係等級1...
生產計畫與控制課設沈理工
目錄第一章.企業簡介 2 第二章.需求 和生產能力平衡 6 第三章.綜合生產計畫的編制和優化 14 第四章.主生產計畫的制定 17 第五章.物料需求計畫 19 第六章.成批生產的生產作業計畫編制 23 第七章.作業排序 29 第八章.課程設計的體會 36 參考文獻 37 1.1企業簡介 上海凱貿實業...