1、精品文檔學校超市選址問題學生姓名專業班級學號題目學校超市選址問題課題性質工程設計課題來源自選課題指導教師同組姓名無對于某一學校超市，其他各單位到其的距離不同，主要內容任務要求參考文獻審查意見同時各單位人員去超市的頻度也不同。請為超市選址，要求實現總體最優。1. 實現公司到超市距離，頻率最優。2. 確定超市位置，要求實現總體最優。 C程序設計第三版譚浩強 著 清華大學出版社數據結構 （ C 語言版）嚴蔚敏著清華大學出版社數據結構及應用沈華等編著機械工業出版社指導教師簽字：教研室主任簽字：。1 歡迎下載精品文檔一、需求分析1 ）核心問題 : 求最短路徑 ( 選址的要求就是超市到各單位權值之和最少

2、)2）數據模型（邏輯結構） : 帶權有向圖 ( 權值計算 : 距離 * 頻度 )3）存儲結構 : typedef structstring vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnum;MGraph;核心算法 : Floyd算法 ( 弗洛伊德算法 - 每一對頂點之間的最短路徑)輸入數據 :各單位名稱，距離，頻度，單位個數輸出數據 :所選單位名稱總體思路 :如果超市是要選在某個單位，那么先用floyd算法得出各頂點間的最短距離 / 最小權值。假設頂點個數有n 個，那么就得到n*n 的

3、一張表格， arcs(i,j)表示 i 單位到 j單位的最短距離 / 最小權值 ,這張表格中和最小的那一行( 假設為第 t 行) ，那么超市選在 t 單位處就是最優解。2 運行環境Visual Stdio C+6.0Windows Vista/2003/XP3 概要設計Floyd 算法利用動態規劃思想， 通過把問題分解為子問題來解決任意兩點見的最短路徑問題。設 G=(V, E, w)是一個帶權有向圖，其邊 V=v1, v2, , vn 。對于 kn，考慮其結點 V 的一個子集。對于 V 中任何兩個結點 vi 、vj ，考慮從vi 到 vj 的中間結點都在 vk 中的所有路徑，設該路徑是其中最短

4、的，并設它的路徑長度為最短路徑長度。如果結點 vk 不在從 vi 到 vj 的最短路徑上，則；反之則可以把分為兩段，其中一段從 vi 到 vk，另一段從 vk 到 vj ，這樣便得到表。1 歡迎下載精品文檔達式。上述討論可以歸納為如下遞歸式：原問題轉化為對每個i 和 j 求，或者說求矩陣流程圖開始Main （）輸入基本信息GreatMgraph（Gh ）建立鄰接矩陣的存儲結構Floyd 算法NYAij=INF,i!=ji 到 j 不存在路Floyed（Gh ）輸出 i->j 的路徑和路徑長度輸出超市的最佳地址：i結束4 詳細設計第一步，讓所有路徑加上中間頂點1，取 Aij與 Ai1+A1

5、j中較小的值作 Aij的新值，完成后得到 A(1), 如此進行下去， 當第 k 步完成后， A。2 歡迎下載精品文檔（ k） ij表示從 i 到就且路徑上的中間頂點的路徑的序號小于或等于k 的最短路徑長度。當第n-1 步完成后，得到 A（ n-1 ），A（n-1 ）即所求結果。 A（n-1 ）ij表示從 i 到 j且路徑上的中點頂點的序號小于或等于n-1 的最短路徑長度，即 A(n-1)ij表示從 i 到 j 的最短路徑長度。4.1 頭文件和變量設定#include <string.h>#include <stdio.h>#include <stdlib.h>

6、;#include <time.h>#include "malloc.h"#include <iostream.h>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767const int MAXVEX=100;typedef char Vextype;4.2 結構體的定義typedef structVextype vexsMAXVEXMAXVEX;/單位名稱（頂點信息）；int adjMAXVEXMAXVEX;/ 單位之

7、間的相通情況（是否有邊）；int disMAXVEXMAXVEX;/ 單位間距離（邊的長度） ；int fMAXVEX;/ 各單位去超市的頻率；。3 歡迎下載精品文檔int n;/ 頂點數和邊數；int e;Mgraph;4.3 變量的輸入void CreatMgraph(Mgraph *G)int i,j,k;printf("請輸入單位個數 :n");scanf("%d",&(G->n);printf("請輸入單位間的路徑數 :n");scanf("%d",&(G->e);printf

8、("請輸入單位名稱 :n");for(i=0;i<G->n;i+)printf("請輸入第 %d個單位名稱 :n",i);scanf("%s",&G->vexsi);for(i=0;i<G->n;i+) / 結構體的初始化； for(j=0;j<G->n;j+)G->adjij=0;G->disij=0;G->fi=0;for(k=0;k<G->e;k+)printf("請輸入相通的兩單位( 輸入格式 :i,j):n");scanf(&

9、quot;%d,%d",&i,&j);/在距離上體現為無向；。4 歡迎下載精品文檔printf("請輸入相同兩個單位間的距離( 格式： dis) ： n");scanf("%d",&(G->disij);G->adjij=1;G->adjji=1;G->disji=G->disij;for(k=0;k<G->n;k+)printf(" 請輸入第 %d個單位去超市的相對頻率 :n",k); scanf("%d",&(G->fk);for(i=0;i<G->n;i+)/以距離和頻率之積作為權值；for(j=0;j<G->n;j+)G->disij*=G->fi;/最終權值非完全無向；if(G->adjij=0&&i!=j)G->disij=INF;4.4 帶權有向圖求最短路徑floyd