D算法的C++实现

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