最短路徑課程設計
① C++課程設計 dijkstra演算法 並行最短路徑
Dijkstra演算法的思想是DP +貪婪。
每次尋找最近的點，擴大和更新的狀態
為（i = 1; <N; + +）/ /擴展N-1
{
T =無窮內大;
K = 1;
為（J = 1，J <N，J + +）/ /這里容是為了找到最近的點，D最小< （/（[J]）&&（D [J] T [K]））
{
噸= D [J];
K =?
}
[K] = 1 ;/ / k點加入的S
（J = 1，J <N，J + +）
（（！ [J]）&&（D [J]>的D [k] + W [K] [J]））/ /更新狀態......基於動態規劃
{
D [J] =的D [k] + W [K] [J];
P [J] = K;
}
>}
不知道LZ在哪裡目前還不清楚
② 最短路徑：拯救007課程設計
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
//#include "Deque.h"
//#include "error.h"
#define ISLAND_DIAMETER 15 /* 小島的直徑 */
#define LAKE_BOUNDARY_X 50 /* 小島到湖邊的距離，在x軸上 */
#define LAKE_BOUNDARY_Y 50 /* 小島到湖邊的距離，在y軸上 */
#define INFINITY 10000 /* 可以跳的步數的最大值 */
typedef unsigned int Vertex;
typedef double Distance;
typedef struct GraphNodeRecord{
int X; /* x軸坐標 */
int Y; /* y軸坐標 */
unsigned int Step; /*跳至該點的步數 */
Vertex Path; /*記錄上一個點 */
} GraphNode;
typedef GraphNode *Graph;
Graph GraphNew(int NodeNum);
void GraphDelete(Graph G);
/* 判斷007是否能從起始處跳至該點(x, y) */
int CheckForStart(int x, int y, Distance d);
/* 判斷007是否能從該點跳至河岸 */
int CheckForEnd(int x, int y, Distance d);
/* 判斷007是否能從點i跳至點j */
int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d);
typedef unsigned int ElemType; /* 在本程序中ElemType指定為int */
/* 鏈表形式 */
typedef struct NodeRecord{
ElemType Element;
struct NodeRecord *Next; /* 指向下一個node */
} *Node;
typedef struct DequeRecord{
Node Front, Rear; /* 分別指向Deque的前後兩個點 */
} *Deque;
Deque DequeNew();
void DequeDelete(Deque D);
void DequeClear(Deque D);
int IsEmpty(Deque D);
void Push(ElemType X, Deque D);
ElemType Pop(Deque D);
void Inject(ElemType X, Deque D);
#define CHECK(X) if(NULL == (X))Error("Out of space!!!")
void Error(const char *msg);
void Warning(const char *msg);
/******創建新的Graph******/
Graph GraphNew(int NodeNum)
{
Graph G;
int i;
if(NodeNum <= 0)return NULL;
G =(GraphNodeRecord *) malloc(NodeNum * sizeof(GraphNode)); /* 分配空間 */
CHECK(G);
for(i = 0; i < NodeNum; i++) /* 初始化 */
{
G[i].X = 0;
G[i].Y = 0;
G[i].Step = INFINITY;
G[i].Path = 0;
}
return G;
}
/******刪除一個Graph)******/
void GraphDelete(Graph G)
{
if(G)free(G);
}
/*******判斷007是否能從起始處跳至該點(x, y)，步長是d******/
int CheckForStart(int x, int y, Distance d)
{
double t;
t = (ISLAND_DIAMETER + (d * 2.0));
return (x*x + y*y) <= t*t/4.0;
/* x^2 + y^2 <= (ISLAND_DIAMETER/2.0 + d)^2 */
}
/*******判斷007是否能從該點跳至河岸，步長是d******/
int CheckForEnd(int x, int y, Distance d)
{
if(x < 0)x = -x; /* 取x的絕對值 */
if(y < 0)y = -y; /* 取y的絕對值 */
return (d >= LAKE_BOUNDARY_X - x) /* 由於湖是個正方形，只需檢查這兩個距離*/
|| (d >= LAKE_BOUNDARY_Y - y);
}
/*******判斷007是否能從點i跳至點j，步長是d******/
int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d)
{
int x, y;
x = g[i].X - g[j].X;
y = g[i].Y - g[j].Y;
return x*x + y*y <= d*d;
}
/******創建新的Deque******/
Deque DequeNew()
{
Deque D;
D =(DequeRecord *) malloc(sizeof(struct DequeRecord));
CHECK(D);
D->Front = D->Rear =(NodeRecord *) malloc(sizeof(struct NodeRecord)); /* 空的頭 */
CHECK(D->Front);
D->Front->Element = 0; /* 初始化 */
D->Rear->Next = NULL;
return D;
}
/******刪除Deque******/
void DequeDelete(Deque D)
{
if(D)
{
while(D->Front)
{
D->Rear = D->Front->Next;
free(D->Front);
D->Front = D->Rear;
}
free(D);
}
}
/******DequeClear刪除所有的節點除了頭節點******/
void DequeClear(Deque D)
{
if(D)
{
while(D->Front->Next) /* 刪除第一個節點 */
{
D->Rear = D->Front->Next->Next;
free(D->Front->Next);
D->Front->Next = D->Rear;
}
D->Rear = D->Front;
}
}
/******判斷Deque是否為空******/
int IsEmpty(Deque D)
{
return D->Front == D->Rear;
}
/******將X元素壓佔到D中******/
void Push(ElemType X, Deque D)
{
Node NewNode;
NewNode =(NodeRecord *) malloc(sizeof(struct NodeRecord)); /* 建立新的節點 */
CHECK(NewNode);
NewNode->Element = X;
NewNode->Next = D->Front->Next;
if(D->Front == D->Rear) /* 如果D為空 */
D->Rear = NewNode;
D->Front->Next = NewNode; /* 壓棧 */
}
/******將第一個元素出棧******/
ElemType Pop(Deque D)
{
Node Temp;
ElemType Item;
if(D->Front == D->Rear)
{
Error("Deque is empty");
return 0;
}
else
{
Temp = D->Front->Next; /* 得到第一個元素 */
D->Front->Next = Temp->Next; /* 重置第一個元素 */
if(Temp == D->Rear) /* 如果只有一個元素 */
D->Rear = D->Front; /* 將D置空 */
Item = Temp->Element;
free(Temp);
return Item;
}
}
/******插入元素X至D末尾******/
void Inject(ElemType X, Deque D)
{
Node NewNode;
NewNode =(NodeRecord *) malloc(sizeof(struct NodeRecord)); /* 創建新節點 */
CHECK(NewNode);
NewNode->Element = X;
NewNode->Next = NULL;
D->Rear->Next = NewNode;
D->Rear = NewNode;
}
/******列印錯誤信息，並退出程序******/
void Error(const char *msg)
{
if(NULL != msg)
fprintf(stderr,"%s\n",msg);
exit(-1);
}
/******列印警告信息，但並不退出程序******/
void Warning(const char *msg)
{
if(NULL != msg)
fprintf(stderr,"%s\n",msg);
}
;
/******讀入一個case返回一個Graph，*Bank 記錄最短到達河岸的路徑******/
Graph read_case(FILE *InFile, int num, Vertex* Bank, Deque D)
{
Graph G = NULL;
Distance JamesJump;
Vertex V;
int x, y;
int i, Times;
*Bank = 0;
fscanf(InFile, "%lf", &JamesJump);
if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/2.0))
{
for(i = 0; i < (num << 1); i++) /*一步便跳出的情況 */
fscanf(InFile, "%d", &x);
*Bank = 1;
}
else if(num > 0) /* 007必須經過鱷魚頭上的情況 */
{
num += 2;
G = GraphNew(num);
for(i = 2; i < num; i++) /* 第三個node開始是鱷魚 */
{
fscanf(InFile, "%d", &x);
fscanf(InFile, "%d", &y);
G[i].X = x;
G[i].Y = y;
if(CheckForStart(x, y, JamesJump)) /*判斷是否能跳上該點*/
{
G[i].Path = 1; /*007可以跳到 */
G[i].Step = 1; /* 一步 */
if(CheckForEnd(x, y, JamesJump)) /* 判斷該點是否能跳出 */
{
*Bank = i; /* 007可以跳出 */
Times = (num - i - 1) << 1;
for(i = 0; i < Times; i++) /* 不必檢驗其他鱷魚 */
fscanf(InFile, "%d", &y);
DequeClear(D);
break;
}
else
Inject(i, D); /* 插入該點，並開始下一個檢測 */
}
}
while(!IsEmpty(D)) /*只經過一個鱷魚無法跳出，必須還要跳到其它鱷魚的情況 */
{
V = Pop(D);
for(i = 2; i < num; i++) /* 從這只鱷魚跳到其他各個鱷魚 */
{
if((G[i].Step > G[V].Step + 1)
&& CheckForConnect(G, V, i, JamesJump))
{
G[i].Path = V;
G[i].Step = G[V].Step + 1;
if((G[i].Step < G[*Bank].Step)
&& CheckForEnd(G[i].X, G[i].Y, JamesJump))
*Bank = i;
else
Inject(i, D);
}
}
}
}
return G;
}
/******寫出結果，即最短路徑******/
void write_result(FILE *OutFile, Vertex Bank, Graph G, Deque D)
{
unsigned int Times, i;
Vertex V;
switch(Bank){
case 0: /* 007無法跳出 */
fprintf(OutFile, "%d\n", -1);
break;
case 1: /* 007可以直接跳出 */
fprintf(OutFile, "%d\n", 1);
break;
default:
Times = G[Bank].Step + 1; /* 跳的步數 */
while(Bank != 1) /* 跟蹤路徑 */
{
Push(Bank, D);
Bank = G[Bank].Path;
}
fprintf(OutFile, "%d\n", Times); /* 輸出 */
for(i = 1; i < Times; i++)
{
V = Pop(D);
fprintf(OutFile, "%d ", G[V].X);
fprintf(OutFile, "%d\n", G[V].Y);
}
}
}
int main(int argc, char *argv[])
{
FILE *in, *out;
Deque D;
int VertexNum;
Graph G = NULL;
Vertex Bank = 0;
in = fopen("input.txt", "r");
if(NULL == in)
{
fprintf(stderr, "Can not open input.txt");
exit(-1);
}
out = fopen("output.txt", "w");
if(NULL == out)
{
fprintf(stderr, "Can not open output.txt");
fclose(in);
exit(-1);
}
D = DequeNew();
while((EOF != fscanf(in, "%d", &VertexNum)) && (0 <= VertexNum))
{
G = read_case(in, VertexNum, &Bank, D); /* 讀文件直到結尾 */
write_result(out, Bank, G, D);
if(G)
GraphDelete(G);
}
fclose(in);
fclose(out);
DequeDelete(D);
return 0;
}
這是你那個網址里的代碼調試通過了，也得到了如例子里的結果。你自己試試吧。
要說明的是請把input.txt和程序放在里一文件夾下再運行程序
③ 軟體課程設計：圖論裡面關於最短路徑的演算法，詳細代碼。 [email protected]
可以憑借Baihi通知我你的題目
有空能完成你無法解決的題目
如果你有相近的要求也能告訴我
ES:\\
交易提醒:預付定金有風險
交易提醒:勿輕信用戶名中的聯系方式
④ 數據結構課程設計作業:求任意兩點的最短路徑問題,寫個完整的程序..急求啊...小弟上學期沒學好..解決加分謝
一：
#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]<<" ";
}
以上二個代碼都是完整可以使用的，樓主喜歡哪個就用那個吧。自己還是可以仔細分析下代碼。
⑤ 數據結構課程序設計: 將地圖存儲20個城市,求任意兩個城市間的最短路徑。
#include<stdio.h>
#include <iostream>
#include<string.h>
using namespace std;
#define M 22
int a[M][M],n,m;
void floyd()
{
int i,j,k;
for(k=0;k<n;k++)
{
(i=0;i<n;i++)
{
if(a[i][k]==0)//0當作無邊
continue;
for(j=0;j<n;j++)
{
if(i==j)//自己到自己
continue;
if(a[k][j]==0)
continue;
if(a[i][j]==0||a[i][k]+a[k][j]<a[i][j])//若當前i到j沒路。或者先到k繞回來，路程更短的話
{
a[i][j]=a[i][k]+a[k][j];
}
}
}
}
}
void main()
{
int i,j;
int p1,p2,w;
while(1)
{
scanf("%d%d",&n,&m);//點數，邊數
memset(a,0,sizeof(a));
for(i=0;i<m;i++)//輸入邊
{
scanf("%d%d%d",&p1,&p2,&w);//p1至p2距離w
//0<=p1,p2<=n-1
if(a[p1][p2]==0||w<a[p1][p2])//無邊，或重邊
{
a[p1][p2]=w;
a[p2][p1]=w;//當無向圖處理
}
}
floyd();
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
}
}
上面有注釋~
最後輸出答案矩陣~
⑥ c++課程設計最短路徑
求單源最短路徑，可以用Dijkstra演算法；求每對頂點之間的最短路徑，可以用Floyed演算法。下面是我以前編的，不過好像有時候不大穩定，沒最終改好，大致演算法實現是這樣的，或許可以參考一下。
a// AdjMatrix.h: interface for the AdjMatrix class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_)
#define AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_
#include <iostream.h>
#include <iomanip.h>
#include "Stack.h"
#define INT_MAX 0x7FFFFFFF
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
template <class Type>
void Make2DArray(Type ** & x,int rows,int cols){//創建二維數組x
x = new Type *[rows];//創建行指針
for(int i = 0;i < rows;i++)//為每一行分配空間
x[i] = new Type[cols];
}
template <class Type>
void Delete2DArray(Type ** & x,int rows){//刪除二維數組x
for(int i = 0;i < rows;i++)//釋放為每一行所分配的空間
delete[]x[i];
delete[]x;//刪除行指針
x = NULL;
}
class AdjMatrix{//方陣類
double **a;//數據緩存區
public:
AdjMatrix(double **b = NULL,int dimention = 0){//初始化方陣
Make2DArray(a,dimention+1,dimention+1);
a[0][0] = dimention;
for(int i = 1,j = 1;i <= dimention,j <= dimention;i++,j++){
a[i][0] = 0;
a[0][j] = 0;
}
if(b)
for(int i1 = 1;i1 <= dimention;i1++)
for(int j1 = 1;j1 <= dimention;j1++)
a[i1][j1] = b[i1-1][j1-1];
}
virtual ~AdjMatrix();//析構函數
AdjMatrix & operator = (const AdjMatrix &);//重載賦值運算符=
void Trs(AdjMatrix &);//矩陣轉置:B=trs(*this)
void Show();//顯示結果
void ShortestPath_Floyed();//弗洛伊德演算法，求每對頂點之間的最短路徑
void ShortestPath_Dijkstra(int);//狄克斯特拉演算法，求單源最短路徑
//輸入v為源點編號
};
#endif // !defined(AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_)
// AdjMatrix.cpp: implementation of the AdjMatrix class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "AdjMatrix.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
AdjMatrix::~AdjMatrix(){
int Dim = (int)a[0][0]+1;
Delete2DArray(a,Dim);
}
AdjMatrix & AdjMatrix::operator = (const AdjMatrix &matrix){
int Dim1 = (int)a[0][0],Dim2 = (int)matrix.a[0][0];
Delete2DArray(a,Dim1+1);
Make2DArray(a,Dim2+1,Dim2+1);
for(int i = 0;i <= Dim2;i++)
for(int j = 0;j <= Dim2;j++)
a[i][j] = matrix.a[i][j];
return *this;
}
void AdjMatrix::Trs(AdjMatrix &B){
int Dim1 = (int)a[0][0],Dim2 = (int)B.a[0][0];
Delete2DArray(B.a,Dim2+1);
Make2DArray(B.a,Dim1+1,Dim1+1);
B.a[0][0] = Dim1;
for(int i = 1,j = 1;i <= Dim1,j <= Dim1;i++,j++){
B.a[i][0] = 0;
B.a[0][j] = 0;
}
for(int i1 = 1;i1 <= Dim1;i1++)
for(int j1 = 1;j1 <= Dim1;j1++)
B.a[i1][j1] = a[j1][i1];
}
void AdjMatrix::Show(){
if((int)a[0][0] == 0)
cerr<<"Error!矩陣不存在!\n";
else{
for(int i = 1;i <= a[0][0];i++){
for(int j = 1;j <= a[0][0];j++){
if(a[i][j] == INT_MAX)
cout<<setw(5)<<setprecision(7)<<"∞"<<'\t';
else
cout<<setw(5)<<setprecision(7)<<a[i][j]<<'\t';
}
cout<<endl;
}
}
}
void AdjMatrix::ShortestPath_Floyed(){
int Dim = (int)a[0][0],pre;
AdjMatrix A,Path;
this->Trs(Path);
Path.Trs(A);//取A=*(this)
for(int i = 1;i <= Dim;i++){
for(int j = 1;j <= Dim;j++)
Path.a[i][j] = -1;
}
for(int k = 1;k <= Dim;k++){
for(int i1 = 1;i1 <= Dim;i1++)
for(int j1 = 1;j1 <= Dim;j1++)
if(A.a[i1][j1] > A.a[i1][k]+A.a[k][j1]){
A.a[i1][j1] = A.a[i1][k]+A.a[k][j1];
Path.a[i1][j1] = k;
}
}
cerr<<"↘Floyed演算法求解如下:\n";
for(int i2 = 1;i2 <=Dim;i2++){//輸出最短路徑
for(int j2 = 1;j2 <=Dim;j2++)
if(i2 != j2){
cout<<" "<<i2<<"->"<<j2<<": ";
if(A.a[i2][j2] == INT_MAX){
if(i2 != j2)
cout<<"不存在路徑!\n";
}
else{
cout<<"路徑長度："<<setw(3)<<A.a[i2][j2]<<" ";
cout<<"路徑："<<i2<<"->";
pre = (int)Path.a[i2][j2];
while(pre != -1){
cout<<pre<<"->";
pre = (int)Path.a[pre][j2];
}
cout<<j2<<endl;
}
}
}
}
void AdjMatrix::ShortestPath_Dijkstra(int v){
int Dim = (int)a[0][0];
AdjMatrix A,temp;
this->Trs(temp);
temp.Trs(A);//取A=*(this)
int *s, *path,u,pre;
s = new int[Dim+1],path = new int[Dim+1];
s[0]=0,path[0]=0;
double *dist,mindis;
dist = new double[Dim+1];
dist[0] = 0.0;
for(int k = 1;k <= Dim;k++){
dist[k] = A.a[v][k];//距離初始化
s[k] = 0;//s[]置空
if(A.a[v][k] < INT_MAX)//路徑初始化
path[k] = v;
else
path[k] = -1;
}
s[v] = 1,path[v] = 0;//源點編號v放入s中
for(int i = 1;i <= Dim;i++){//循環直到所有頂點的最短路徑都求出
mindis = INT_MAX;
u = -1;
for(int j = 1;j <= Dim;j++){//選取不在s中且具有最小距離的頂點u
if(s[j] == 0 && dist[j] < mindis){
u = j;
mindis = dist[j];
}
}
if(u != -1){
s[u] = 1;
for(int r = 1;r <= Dim;r++)
if(s[r] == 0)
if(A.a[u][r] < INT_MAX && dist[u]+A.a[u][r] < dist[r]){
dist[r] = dist[u]+A.a[u][r];
path[r] = u;
}
}
}
cout<<"↘Dijkstra演算法求解如下：\n";
Stack<int> st;
for(int i1 = 1;i1 <= Dim;i1++){//輸出最短路徑的長度，路徑逆序輸出
if(i1 != v){
cout<<" "<<v<<"->"<<i1<<": ";
if(s[i1] == 1){
cout<<"路徑長度："<<setw(3)<<dist[i1]<<" ";
pre = i1;
cout<<"路徑：";
while(pre != v){//一直回溯到初始頂點
st.Push(pre);
pre = path[pre];
}
st.Push(pre);
while(0 < st.GetTop() ){
cout<<st.Pop()<<"->";
}
cout<<st.Pop()<<endl;
}
else
cout<<"不存在路徑!\n";
}
}
}
// Stack.h: interface for the Stack class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_)
#define AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_
#include<iostream.h>
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#define MaxSize 1024
template <class Type> class Stack{//堆棧類
private:
Type data[MaxSize];
int top;
public:
Stack(){ //初始化棧
top = -1;
}
virtual~Stack();
bool IsEmpty(); //判斷棧為空
bool IsFull(); //判斷棧為滿
int GetTop(); //取top的位置
void Push(Type);//進棧
Type Pop(); //退棧
};
template <class Type> Stack<Type>::~Stack(){
}
template <class Type> bool Stack<Type>::IsEmpty(){
return(top == -1);
}
template <class Type> bool Stack<Type>::IsFull(){
return(top == MaxSize-1);
}
template <class Type> int Stack<Type>::GetTop(){
return top;
}
template <class Type> void Stack<Type>::Push(Type item){
if(IsFull())
cout<<"棧滿!\n";
else{
top++;
data[top] = item;
}
}
template <class Type> Type Stack<Type>::Pop(){
if(IsEmpty()){
cout<<"棧空!\n";
return NULL;
}
else{
Type item;
item = data[top];
top--;
return item;
}
}
#endif // !defined(AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_)
⑦ 關於最短路徑的C語言課程設計 有會的嗎QQ476566409！！！很急~~
你好，這是我寫的D氏演算法求解：
－－－－－－－－－－－－－－－－－－－－－－－－－
#include<stdio.h>
#define MAX 200
#define N 5
void main()
{
int final[N]={0},D[N],G[N][N],P[N][N]={0},i,j,e,h,w,min;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
G[i][j]=MAX;
printf("請輸入有向線路條數:");scanf("%d",&e);
printf("\n請輸入線路頭尾及長度:\n");
for(i=0;i<e;i++)
{
scanf("%d%d%d",&h,&w,&j);G[h][w]=j;
}
printf("\n請輸入路徑起始點:");scanf("%d%d",&h,&w);
for(i=0;i<N;i++)
{
D[i]=G[h][i];
if(D[i]<MAX)
{P[i][h]=1;P[i][i]=2;}
}
final[h]=1;D[h]=0;
for(i=1;i<N;i++)
{min=MAX;
for(j=0;j<N;j++)
if(!final[j])
if(D[j]<min)
{e=j;min=D[j];}
final[e]=1;
for(j=0;j<N;j++)
if(!final[j]&&min+G[e][j]<D[j])
{D[j]=min+G[e][j];
for(h=0;h<N;h++)
P[j][h]=P[e][h];
P[j][j]=P[j][e]+1;
}
}
printf("\n最短路程為:%d",D[w]);
printf("\n最短路徑為:");
for(j=1;j<=N;j++)
for(i=0;i<N;i++)
if(P[w][i]==j)
{printf("%d ",i);}
printf("\n");
}
－－－－－－－－－－－－－－－－－－－－－－－－