資源簡介
D算法的C++實現,通信網理論中的最短路徑算法。求出最短路徑及其權值

代碼片段和文件信息
#include?“iostream.h“
#include?“malloc.h“
#define?Max?20
#define?INFINITY?100
struct?MGraph
{
int?vexnumarcnum;
int?**info;
}MGraph;
int?Locate(char?str[]int?nchar?ch)
{
for(int?i=0;i if(ch==str[i])?return?i;
return?-1;
}
void?CreateArray(char?str[]int?n)
{
int?kijarweight;
char?ht;
ar=MGraph.arcnum;
MGraph.info=(int?**)malloc(n*sizeof(int?*));
for(i=0;i {
MGraph.info[i]=(int*)malloc(sizeof(int));
}
for(i=0;i for(j=0;j MGraph.info[i][j]=INFINITY;
int graph_type;
cout<<“輸入為:0:無向圖?1:有向圖“< cin>>graph_type;
if(graph_type==0)
{
cout<<“輸入圖中的弧和權值:“< for(i=0;i {
cin>>h>>t>>weight;
j=Locate(strnt);
k=Locate(strnh);
while(j<0||k<0)
{
cout<<“有的頂點不存在請重新輸入!“< cin>>t>>h;
j=Locate(strnt);
k=Locate(strnh);
}
MGraph.info[k][j]=weight;
MGraph.info[j][k]=weight;
}
}
else
{
cout<<“輸入權值矩陣“< for(i=0;i for(j=0;j {
cin>>weight;
MGraph.info[i][j]=weight;
}
}
}
void?ShortPath(char?chchar?string[]int?m)
{
int?ijminvkt;
int?*final**q*D;
k=Locate(stringmch);
D=new?int[MGraph.vexnum];
q=(int?**)malloc(MGraph.vexnum*sizeof(int?*));
for(i=0;i q[i]=(int*)malloc(sizeof(int));
final=new?int[m];
for(i=0;i {
final[i]=0;D[i]=MGraph.info[k][i];
for(j=0;j if(D[i] {
q[i][k]=1;q[i][i]=1;
}
}
D[k]=0;final[k]=1;
for(i=1;i {
min=INFINITY;
for(j=0;j if(!final[j])
if(D[j] final[v]=1;
for(int?w=0;w if(!final[w]?&&?(min+MGraph.info[v][w]) {
D[w]=min+MGraph.info[v][w];
for(t=0;t q[w][t]=q[v][t];
q[w][w]=1;
}
}
for(i=0;i {
????????if(i!=k)
{
????????????cout< if(D[i] ????????????{
for(int?j=0;j if(q[i][j]&&j!=i)
cout< cout<
cout<<“長度:“< }
else
cout<<“不存在!“< }??
}
}
int?main()
{
int?vaik;
char?vexs[Max]ch;
cout<<“輸入頂點數:“;cin>>v;
cout<<“輸入弧數:“;cin>>a;
MGraph.arcnum=a;MGraph.vexnum=v;
cout<<“輸入頂點的名字:“;
for(i=0;i cin>>vexs[i];
CreateArray(vexsv);
cout<<“輸入一個頂點:“;
cin>>ch;
k=Locate(vexsvch);
while(k<0)
{
cout<<“輸入有誤請重新輸入:“;
cin>>ch;
k=Locate(vexsvch);
}
ShortPath(chvexsv);
return?0;
}
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????2798??2012-04-02?10:27??d_algorithm\d.cpp
?????文件??????11794??2012-04-02?10:27??d_algorithm\Debug\d.obj
?????文件??????????0??2012-04-02?10:27??d_algorithm\Debug\d.sbr
?????文件??????66560??2012-04-02?10:27??d_algorithm\Debug\d_algorithm.bsc
?????文件??????94270??2012-04-02?10:27??d_algorithm\Debug\d_algorithm.exe
?????文件??????58304??2012-04-02?10:27??d_algorithm\Debug\d_algorithm.ilk
?????文件?????525312??2012-04-02?10:27??d_algorithm\Debug\d_algorithm.pdb
?????文件??????50176??2012-04-02?10:47??d_algorithm\Debug\vc60.idb
?????文件??????61440??2012-04-02?10:27??d_algorithm\Debug\vc60.pdb
?????文件???????4081??2012-04-02?09:29??d_algorithm\d_algorithm.dsp
?????文件????????530??2012-04-01?11:33??d_algorithm\d_algorithm.dsw
?????文件??????41984??2012-04-02?11:14??d_algorithm\d_algorithm.ncb
?????文件??????48640??2012-04-02?11:14??d_algorithm\d_algorithm.opt
?????文件???????1022??2012-04-02?10:27??d_algorithm\d_algorithm.plg
?????目錄??????????0??2012-05-11?08:52??d_algorithm\Debug
?????目錄??????????0??2012-05-11?08:52??d_algorithm
-----------?---------??----------?-----??----
???????????????966911????????????????????16
評論
共有 條評論