數據結構課程設計最優路徑
Ⅰ 數據結構課程設計作業:求任意兩點的最短路徑問題,寫個完整的程序..急求啊...小弟上學期沒學好..解決加分謝
一：
#include "stdafx.h"
#include <limits>
#include <iostream>
#include <fstream>
using namespace std;
const int MAXINT = numeric_limits<int>::max();
template <class Type>
void Dijkstra(int n, int v, Type dist[], int prev[], Type** c)
{
bool *s = new bool[n+1];
int i, j;
for(i = 1; i <=n; i++)
{
dist[i] = c[v][i];
if(c[v][i]!=MAXINT)
prev[i] = v;
else prev[i] =0;
s[i] = false;
}
s[v] = true;
dist[v] = 0;
prev[v] = 0;
for(i = 1; i< n; i++)
{
int u = v;
int temp = MAXINT;
for( j = 1; j<=n; j++)
if(!s[j]&&dist[j]<temp)
{
u = j;
temp = dist[j];
}
s[u] = true;
for(j=1; j<=n; j++)
{
if((!s[j])&&c[u][j]<MAXINT)
{
if((dist[u]+c[u][j])<dist[j])
{
dist[j] = dist[u] + c[u][j];
prev[j] = u;
}
}
}
}
delete [] s;
}
void djpath(int m, int v, int prev[])
{
int i = m ,j =1;
while(i!=0)
{
if (j == 1)
{
cout<< i;
j = 0;
}
else
cout<< "-" << i;
i = prev[i];
}
cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"最大整數:"<<MAXINT<<endl;
int prev[6], dist[6];
int i,j,n;
int** myc;
FILE *fp;
fp=fopen("data.txt", "r");
fscanf(fp,"%d", &n);
myc = new int* [n+1];
for(i =0; i<=n; i++)
myc[i] = new int[n+1];
for(i=1; i<=n; i++)
for(j =1; j<=n; j++)
{
fscanf(fp, "%d",&myc[i][j]);
if (myc[i][j]==-1)
myc[i][j] = MAXINT;
}
Dijkstra(5, 1, dist, prev, myc);
for(i = 1; i<=5; i++)
cout<<dist[i]<<endl;
for(i=2; i<=5; i++)
djpath(i,1,prev);
for(i = 0; i<=5; i++)
delete[] myc[i];
delete [] myc;
return 0;
}
輸入數據採用文本文件格式，下面是data.txt的內容:
5
0 10 -1 30 100
10 0 50 -1 -1
-1 50 0 20 10
30 -1 20 0 60
100 -1 10 60 0
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/mikewolf2009/archive/2009/09/12/4545537.aspx
二：
#include<iostream>
using namespace std;
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;
d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];
for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}
for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;} //在藍點集中選擇一個最短距離最小的藍點k來擴充紅點集是Dijkstra演算法的關鍵
s[k]=1;//point k join the S
for (j=1;j<n;j++) //將k擴充到紅點後，剩餘藍點集的估計距離可能由於增加了新紅點k而減小，此時必須調整相應藍點的估計距離。對於任意的藍點j，若k由藍變紅後使D[j]變小，則必定是由於存在一條從s到j且包含新紅點k的更短路徑：P=<s，…，k，j>。且D[j]減小的新路徑P只可能是由於路徑<s，…，k>和邊<k，j>組成。所以，當length(P)=D[k]+w<k，j>小於D[j]時，應該用P的長度來修改D[j]的值。
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}
}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";
}
以上二個代碼都是完整可以使用的，樓主喜歡哪個就用那個吧。自己還是可以仔細分析下代碼。
Ⅱ 求一份數據結構課程設計 題目：校園導航 要求：平面圖、最短路徑 謝謝各位大神
詳細情況到上海松江區樂都路251號10樓L座新科
Ⅲ 數據結構課程設計--用C#語言解決最短路徑的問題
網路上可以找到代碼吧。點到其餘點最短路用迪傑斯特拉演算法，任意兩點間最短路用弗洛伊德演算法
Ⅳ 數據結構課程設計—最短路徑
#include <stdio.h>
#define INFINITY 10000
#define TRUE 1
#define FALSE 0
#define VERTEX_NUM 6
typedef struct Graph
{
char vexs[VERTEX_NUM]; /*頂點*/
int arcs[VERTEX_NUM][VERTEX_NUM]; /*鄰接矩陣*/
int vexnum; /*頂點數專*/
int arcnum; /*弧數屬*/
}Graph;
Ⅳ 數據結構課程設計最短路徑的求解 這是程序，出現錯誤了，不知道怎麼改
數據結構課程設計 怎麼做]de
Ⅵ 跪求一份迷宮的最短路徑的數據結構課程設計!!!急急急!!!!!!!
基本思路是：1．從入口進入迷宮之後，不管在迷宮的哪一個位置上，都是先往東走，如果走得通就繼續往東走，如果在某個位置上往東走不通的話，就依次試探往南、往西和往北的方向，依著某個走得通的方向繼續往前直到出口為止；
2．如果在某個位置上四個方向都走不通的話，就退回到前一個位置，換一個方向再試，如果這個位置已經沒有方向可試了就再退一步，如果所有已經走過的位置的四個方向都試探過了，一直退到起始點都沒有走通，那就說明這個迷宮根本不通；
若當前位置「可通」，則納入路徑，繼續前進;
若當前位置「不可通」，則後退，換方向繼續探索;
若四周「均無通路」，則將當前位置從路徑中刪除出去。我這只有演算法（利用的是棧）：設定當前位置的初值為入口位置；
do｛
若當前位置可通，
則｛將當前位置插入棧頂；
若該位置是出口位置，則演算法結束；
否則切換當前位置的東鄰方塊為
新的當前位置；｝
否則 { ......｝
｝while (棧不空）；
若棧不空且棧頂位置尚有其他方向未被探索，
則設定新的當前位置為: 沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；
若棧不空但棧頂位置的四周均不可通，
則｛刪去棧頂位置；// 從路徑中刪去該通道塊
若棧不空，則重新測試新的棧頂位置，
直至找到一個可通的相鄰塊或出棧至棧空；
｝
若棧空，則表明迷宮沒有通路。具體程序自己寫吧！謝謝！
Ⅶ 數據結構課程設計應該把文件存儲在哪裡
首先想清楚什麼數來據存內存，源什麼數據存文件。
一般來講，參與邏輯運算的標志位，中間變數，計數器存內存；需要顯示的東西、實時的東西先存內存，挑選你要存文件的東西存文件；存內存的意思是當進程結束這些東西都會被釋放回收。
給用戶設置參數的配置信息存文件，還有需要查看的歷史信息存文件。
存在哪裡這個基本不需要考慮吧，開始你就存在工程目錄下比較方便，這樣打開和保存的時候都不需要寫路徑。
至於存什麼格式的文件無關緊要，關鍵是搞好讀取文件的方式，然後就存成txt好了。有段時間我下電影經常下到PDF格式的電影，幾個G的PDF你敢信？然後直接用播放器播放一樣能看