杨村红灰相间的校服:Dijkstra算法算最短路径

////////////////////////////////////////////////////////////
// Graph.h
#pragma once

#define maxPoint 100

class CGraph
{
public:
CGraph(void);
~CGraph(void);

bool SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size );
bool Dijkstra();
void Display();
int GetStartPoint();
double GetBestWay( int dest , int path[] , int &pathLen );
private:
//标志当前图是否已经求解
bool solved;
//当前图布局
double graph[maxPoint][maxPoint];
//地图大小
int size;
//起点
int startPoint;
//当前图的解
double dist[maxPoint];
int prev[maxPoint];
};

////////////////////////////////////////////////////////////
// Graph.cpp
#include 'StdAfx.h'
#include '.\graph.h'

CGraph::CGraph(void)
{
for( int i = 0 ; i < maxPoint ; i++ )
{
for( int j = 0 ; j < maxPoint ; j++ )
graph[i][j] = -1;
}
startPoint = -1;
size = -1;
//当前图还没有求解
solved = false;
}

CGraph::~CGraph(void)
{
}
//
//
bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size )
{
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
graph[i][j] = g[i][j];
}
this->startPoint = startPoint;
this->size = size;
solved = false;

Dijkstra();
return true;
}
//
//
bool CGraph::Dijkstra()
{
bool s[maxPoint];
for( int j = 0 ; j < size ; j++ )
{
dist[j] = graph[startPoint][j];
s[j] = false;
//dist[i]<0，表示没有路径连接 结点startPoint 与 结点j
if( dist[j] < 0 )
prev[j] = 0;
else
prev[j] = startPoint;
}
//从起点出发
dist[startPoint] = 0;
s[startPoint] = true;
for( int i = 0 ; i < size ; i++ )
{
double temp;
int u = startPoint;
bool flag = false;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] )
{
//如果不是第一次比较，temp u，都已经赋值，则
if( flag )
{
if( dist[j] > 0 && dist[j] < temp )
{
u = j;
temp = dist[j];
}
}
else
{
u = j;
temp = dist[j];
flag = true;
}
}
}
s[u] = true;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] && graph[u][j] > 0 )
{
double newDist = dist[u] + graph[u][j];
if( dist[j] < 0 || newDist < dist[j] )
{
dist[j] = newDist;
prev[j] = u;
}
}
}
}
//标记当前问题已经解决
solved = true;
return true;
}
//
//
void CGraph::Display()
{
printf( '当前地图的邻接矩阵\n' );
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
{
printf( '%5.f' , graph[i][j] );
}
printf( '\n' );
}
}
//
//
double CGraph::GetBestWay( int dest , int path[] , int &pathLen )
{
int p = dest;
int theway[maxPoint];
int len = 0;
while( p != startPoint )
{
theway[len] = p;
p = prev[p];
len++;
}
theway[len] = startPoint;
len++;
for( int i = 0 , j = len - 1 ; i < len ; i++ , j-- )
path[i] = theway[j];
pathLen = len;
return dist[dest];
}
//
//
int CGraph::GetStartPoint()
{
return startPoint;
}
//

////////////////////////////////////////////////////////////
// Dijkstra.cpp : 定义控制台应用程序的入口点。
//

#include 'stdafx.h'
#include 'conio.h'
#include 'Graph.h'

int _tmain(int argc, _TCHAR* argv[])
{
double graph[][maxPoint] =
{
{ 1 , 10 , -1 , 30 , 100 } ,
{ -1 , 0 , 50 , -1 , -1 } ,
{ -1 , -1 , 0 , -1 , 10 } ,
{ -1 , -1 , 20 , 0 , 60 } ,
{ -1 , -1 , -1 , -1 , -1 }
};
int size = 5;
int start = 0;
int dest = 1;
int pathlen;
int path[maxPoint];
double dist;

CGraph g;
g.SetGraph( graph , start , size );
g.Display();
printf( '----------------------------------------\n' );
for( dest = 0 ; dest < size ; dest++ )
{
dist = g.GetBestWay( dest , path , pathlen );

printf( '从 %d 到 %d 的最短路径长 %.f\n' , g.GetStartPoint() , dest , dist );
printf( '所经结点为:\n' );
for( int i = 0 ; i < pathlen ; i++ )
printf( '%3d' , path[i] );
printf( '\n----------------------------------------\n' );
}
getch();
return 0;
}

////////////////////////////////////////////////////////////
// 程序说明：
// 本程序在 VC++.NET 2003 上调试通过
// 首先建立 Win32控制台应用程序，工程名为 Dijkstra
// 工程设置默认
// 添加 一般C++类 CGraph
// 填写以上内容

////////////////////////////////////////////////////////////
// Graph.h
#pragma once

#define maxPoint 100

class CGraph
{
public:
CGraph(void);
~CGraph(void);

bool SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size );
bool Dijkstra();
void Display();
int GetStartPoint();
double GetBestWay( int dest , int path[] , int &pathLen );
private:
//标志当前图是否已经求解
bool solved;
//当前图布局
double graph[maxPoint][maxPoint];
//地图大小
int size;
//起点
int startPoint;
//当前图的解
double dist[maxPoint];
int prev[maxPoint];
};

////////////////////////////////////////////////////////////
// Graph.cpp
#include 'StdAfx.h'
#include '.\graph.h'

CGraph::CGraph(void)
{
for( int i = 0 ; i < maxPoint ; i++ )
{
for( int j = 0 ; j < maxPoint ; j++ )
graph[i][j] = -1;
}
startPoint = -1;
size = -1;
//当前图还没有求解
solved = false;
}

CGraph::~CGraph(void)
{
}
//
//
bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size )
{
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
graph[i][j] = g[i][j];
}
this->startPoint = startPoint;
this->size = size;
solved = false;

Dijkstra();
return true;
}
//
//
bool CGraph::Dijkstra()
{
bool s[maxPoint];
for( int j = 0 ; j < size ; j++ )
{
dist[j] = graph[startPoint][j];
s[j] = false;
//dist[i]<0，表示没有路径连接 结点startPoint 与 结点j
if( dist[j] < 0 )
prev[j] = 0;
else
prev[j] = startPoint;
}
//从起点出发
dist[startPoint] = 0;
s[startPoint] = true;
for( int i = 0 ; i < size ; i++ )
{
double temp;
int u = startPoint;
bool flag = false;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] )
{
//如果不是第一次比较，temp u，都已经赋值，则
if( flag )
{
if( dist[j] > 0 && dist[j] < temp )
{
u = j;
temp = dist[j];
}
}
else
{
u = j;
temp = dist[j];
flag = true;
}
}
}
s[u] = true;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] && graph[u][j] > 0 )
{
double newDist = dist[u] + graph[u][j];
if( dist[j] < 0 || newDist < dist[j] )
{
dist[j] = newDist;
prev[j] = u;
}
}
}
}
//标记当前问题已经解决
solved = true;
return true;
}
//
//
void CGraph::Display()
{
printf( '当前地图的邻接矩阵\n' );
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
{
printf( '%5.f' , graph[i][j] );
}
printf( '\n' );
}
}
//
//
double CGraph::GetBestWay( int dest , int path[] , int &pathLen )
{
int p = dest;
int theway[maxPoint];
int len = 0;
while( p != startPoint )
{
theway[len] = p;
p = prev[p];
len++;
}
theway[len] = startPoint;
len++;
for( int i = 0 , j = len - 1 ; i < len ; i++ , j-- )
path[i] = theway[j];
pathLen = len;
return dist[dest];
}
//
//
int CGraph::GetStartPoint()
{
return startPoint;
}
//

////////////////////////////////////////////////////////////
// Dijkstra.cpp : 定义控制台应用程序的入口点。
//

#include 'stdafx.h'
#include 'conio.h'
#include 'Graph.h'

int _tmain(int argc, _TCHAR* argv[])
{
double graph[][maxPoint] =
{
{ 1 , 10 , -1 , 30 , 100 } ,
{ -1 , 0 , 50 , -1 , -1 } ,
{ -1 , -1 , 0 , -1 , 10 } ,
{ -1 , -1 , 20 , 0 , 60 } ,
{ -1 , -1 , -1 , -1 , -1 }
};
int size = 5;
int start = 0;
int dest = 1;
int pathlen;
int path[maxPoint];
double dist;

CGraph g;
g.SetGraph( graph , start , size );
g.Display();
printf( '----------------------------------------\n' );
for( dest = 0 ; dest < size ; dest++ )
{
dist = g.GetBestWay( dest , path , pathlen );

printf( '从 %d 到 %d 的最短路径长 %.f\n' , g.GetStartPoint() , dest , dist );
printf( '所经结点为:\n' );
for( int i = 0 ; i < pathlen ; i++ )
printf( '%3d' , path[i] );
printf( '\n----------------------------------------\n' );
}
getch();
return 0;
}

////////////////////////////////////////////////////////////
// 程序说明：
// 本程序在 VC++.NET 2003 上调试通过
// 首先建立 Win32控制台应用程序，工程名为 Dijkstra
// 工程设置默认
// 添加 一般C++类 CGraph
// 填写以上内容

////////////////////////////////////////////////////////////
// Graph.h
#pragma once

#define maxPoint 100

class CGraph
{
public:
CGraph(void);
~CGraph(void);

bool SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size );
bool Dijkstra();
void Display();
int GetStartPoint();
double GetBestWay( int dest , int path[] , int &pathLen );
private:
//标志当前图是否已经求解
bool solved;
//当前图布局
double graph[maxPoint][maxPoint];
//地图大小
int size;
//起点
int startPoint;
//当前图的解
double dist[maxPoint];
int prev[maxPoint];
};

////////////////////////////////////////////////////////////
// Graph.cpp
#include 'StdAfx.h'
#include '.\graph.h'

CGraph::CGraph(void)
{
for( int i = 0 ; i < maxPoint ; i++ )
{
for( int j = 0 ; j < maxPoint ; j++ )
graph[i][j] = -1;
}
startPoint = -1;
size = -1;
//当前图还没有求解
solved = false;
}

CGraph::~CGraph(void)
{
}
//
//
bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size )
{
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
graph[i][j] = g[i][j];
}
this->startPoint = startPoint;
this->size = size;
solved = false;

Dijkstra();
return true;
}
//
//
bool CGraph::Dijkstra()
{
bool s[maxPoint];
for( int j = 0 ; j < size ; j++ )
{
dist[j] = graph[startPoint][j];
s[j] = false;
//dist[i]<0，表示没有路径连接 结点startPoint 与 结点j
if( dist[j] < 0 )
prev[j] = 0;
else
prev[j] = startPoint;
}
//从起点出发
dist[startPoint] = 0;
s[startPoint] = true;
for( int i = 0 ; i < size ; i++ )
{
double temp;
int u = startPoint;
bool flag = false;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] )
{
//如果不是第一次比较，temp u，都已经赋值，则
if( flag )
{
if( dist[j] > 0 && dist[j] < temp )
{
u = j;
temp = dist[j];
}
}
else
{
u = j;
temp = dist[j];
flag = true;
}
}
}
s[u] = true;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] && graph[u][j] > 0 )
{
double newDist = dist[u] + graph[u][j];
if( dist[j] < 0 || newDist < dist[j] )
{
dist[j] = newDist;
prev[j] = u;
}
}
}
}
//标记当前问题已经解决
solved = true;
return true;
}
//
//
void CGraph::Display()
{
printf( '当前地图的邻接矩阵\n' );
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
{
printf( '%5.f' , graph[i][j] );
}
printf( '\n' );
}
}
//
//
double CGraph::GetBestWay( int dest , int path[] , int &pathLen )
{
int p = dest;
int theway[maxPoint];
int len = 0;
while( p != startPoint )
{
theway[len] = p;
p = prev[p];
len++;
}
theway[len] = startPoint;
len++;
for( int i = 0 , j = len - 1 ; i < len ; i++ , j-- )
path[i] = theway[j];
pathLen = len;
return dist[dest];
}
//
//
int CGraph::GetStartPoint()
{
return startPoint;
}
//

////////////////////////////////////////////////////////////
// Dijkstra.cpp : 定义控制台应用程序的入口点。
//

#include 'stdafx.h'
#include 'conio.h'
#include 'Graph.h'

int _tmain(int argc, _TCHAR* argv[])
{
double graph[][maxPoint] =
{
{ 1 , 10 , -1 , 30 , 100 } ,
{ -1 , 0 , 50 , -1 , -1 } ,
{ -1 , -1 , 0 , -1 , 10 } ,
{ -1 , -1 , 20 , 0 , 60 } ,
{ -1 , -1 , -1 , -1 , -1 }
};
int size = 5;
int start = 0;
int dest = 1;
int pathlen;
int path[maxPoint];
double dist;

CGraph g;
g.SetGraph( graph , start , size );
g.Display();
printf( '----------------------------------------\n' );
for( dest = 0 ; dest < size ; dest++ )
{
dist = g.GetBestWay( dest , path , pathlen );

printf( '从 %d 到 %d 的最短路径长 %.f\n' , g.GetStartPoint() , dest , dist );
printf( '所经结点为:\n' );
for( int i = 0 ; i < pathlen ; i++ )
printf( '%3d' , path[i] );
printf( '\n----------------------------------------\n' );
}
getch();
return 0;
}

////////////////////////////////////////////////////////////
// 程序说明：
// 本程序在 VC++.NET 2003 上调试通过
// 首先建立 Win32控制台应用程序，工程名为 Dijkstra
// 工程设置默认
// 添加 一般C++类 CGraph
// 填写以上内容

[图算法]Dijkstra算法
主要的算法描述是这样的
L(x)标示由结点a到结点x的长度,算法结束时,L(z)表示的是从a到z的最短长度 .
Prodedure Dijkstra (G:所有权都为正数的加权连通简单图)
{G带有顶点a=v0,v1,…,vn-1,vn=z和权w(vi,vj),若{vi,vj}不是G中的边,则w(vi,vj)=无穷大}
For i:=1 to n
L(vi):=无穷大
L(a):=0
S:=空集
{初始化标记:a的标记为0,其余结点标记为无穷大,程序中可以用一个很大的整数代替,S是空集}
While z不属于S
Begin
U:=不属于S的L(u)最小的一个顶点
S:=S并上{u}
For 所有不属于S的顶点v
If(L(u)+w(u,v)<L(v))
Then L(v):=L(u)+w(u,v)
{这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记}
End{L(z)=从a到z的最短路的长度}

通常实现时,
1)要用到字典来存结果,这里仅通过输出结果做简单处理.
2)本来通常在这个算法里用的优先队列也改用一个结构体矩阵简化代替.
/* Dijkstra算法(简单数据类型实现)

*/

#include "Global.h"
#include <stdio.h>
#ifndef DijkstraAlgorithm_H
#define DijkstraAlgorithm_H
typedef struct
{
int selected;
int l_u; /*Now Length From the Start Node*/
int id;
char name;
}dNode;

extern int minNodeUnSelected(dNode* myNode,int len);
extern void shortestLenAdjust(dNode *myNode,Type** wArr,int len,int u);/*shortest path length adjust*/

#endif

int minNodeUnSelected(dNode* myNode,int len)/*seleted the nearest node*/
{
int findFirst=0;
int currentMinIndex=0;
int i=0;/*iterator control*/

assertF(myNode!=NULL,"in minNodeUnSelected ,myNode is null\n");

for(i=0;i<len;i++)
{
if(!myNode[i].selected)
{
/*Core Idea*/
/*
if L(u)+w(u,v)<L(v) then
L(v)=L(u)+w(u,v)
*/
if(!findFirst)
{
findFirst=1;
currentMinIndex=i;
}
else
{
if(myNode[i].l_u<myNode[currentMinIndex].l_u)
currentMinIndex=i;
}
}
}
assertF(findFirst==1,"in minNodeUnSelected ,findFirst is null\n");
myNode[currentMinIndex].selected=1;
return currentMinIndex;
}

void shortestLenAdjust(dNode *myNode,Type** wArr,int len,int u)/*shortest path length adjust*/
{
int v=0;/*iterator num*/
assertF(myNode!=NULL,"in shortestLenAdjust,myNode is NULL\n");
assertF(wArr!=NULL,"in minNodeUnSelected ,wArr is null\n");
for(v=0;v<len;v++)
{
if(!myNode[v].selected)
{
/*core idea*/
if(myNode[u].l_u+wArr[u][v]<myNode[v].l_u)
myNode[v].l_u=myNode[u].l_u+wArr[u][v];

}
}
}

/*Dijkstra Algorithm test program*/
#include "Global.h"
#include "Ulti.h"
#include "SortAlgorithm.h"
#include "DijkstraAlgorithm.h"
#include "MyAssert.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *inFileName="inputData.txt";
/*
input data specification
row,col,
startNodeId,endNodeId,should obey the rule in C Language.Start from 0
wArr
{
, , , ,
, , , ,
, , , ,
}
*/

char *outFileName="outputData.txt";
#define DEBUG 1

void main(int argc,char* argv[])
{
FILE *inputFile;/*input file*/
FILE *outputFile;/*output file*/

double startTime,endTime,tweenTime;/*time callopsed info*/

int row,col;
Type** wArr;

int i,j;/*iterator index*/
int n;/*arr deminision for squre matrix*/

char* ansList;/*the answer list to get the shortest path info*/
int curAnsCharLen;/*the len of the ansList char* */
int u;/*The temp nearest node id*/
int startNodeId,endNodeId;/*the start and end node location*/
dNode* myNode;

int tmpLen;/*temp data*/

int posAdjust=0;

/*input file open*/
if(argc>1)strcpy(inFileName,argv[1]);
assertF((inputFile=fopen(inFileName,"rb"))!=NULL,"input file error");
printf("input file open success\n");

/*outpout file open*/
if(argc>2)strcpy(outFileName,argv[2]);
assertF((outputFile=fopen(outFileName,"wb"))!=NULL,"output file error");
printf("output file open success\n");

/*start data read in*/
fscanf(inputFile,"%d,%d,",&row,&col);
fscanf(inputFile,"%d,%d,",&startNodeId,&endNodeId);

/*****************data init*****************/
/****argu prepare****/
assertF(col==row,"in test col!=row");
n=row;/*get the size of square matrix*/
/*myNode memory apply*/
myNode=(dNode*)malloc(sizeof(dNode)*n);

for(i=0;i<n;i++)
{
myNode[i].selected=0;
myNode[i].id=i;
myNode[i].l_u=IntLimit;
}

ansList=(char*)malloc(sizeof(char)*n*4);/*only could tackle with gLen<100*/
/*clean the rubbish strings*/
tmpLen=sizeof(char)*n*4;
for(i=0;i<tmpLen;i++)
{
ansList[i]='\0';
}

/*************end of data init******************/

/*Memory Apply*/
wArr=(Type**)malloc(sizeof(Type*)*row);
for(i=0;i<row;i++)
wArr[i]=(Type*)malloc(sizeof(Type)*col);

/*Read 2d arr data*/
for(i=0;i<row;i++)
{
for(j=0;j<col-1;j++)
fscanf(inputFile,"%d,",&wArr[i][j]);
fscanf(inputFile,"%d;",&wArr[i][j]);
}
/*big length adjust*/
for(i=0;i<row;i++)
for(j=0;j<col;j++)
if(wArr[i][j]==-1)wArr[i][j]=IntLimit;

show2DArr(wArr,row,col);

#if DEBUG
printf("\n*******start of test program******\n");
printf("now is runnig,please wait...\n");
startTime=(double)clock()/(double)CLOCKS_PER_SEC;
/******************Core program code*************/

curAnsCharLen=0;/*the set of the answer should be empty*/
myNode[startNodeId].l_u=0;

fprintf(outputFile,"The shortest path's node sequence using dijkstra algorithm in this Graph is:\r\n");
while(!myNode[endNodeId].selected)
{
u=minNodeUnSelected(myNode,n);/*seleted the nearest node*/
//addToAnsList(ansList,&curAnsCharPos,u);/*add it to the answer list*/
/*output the shortest path*/
fprintf(outputFile,"%d,",u);
if(posAdjust++>10)
{
posAdjust=0;
fprintf(outputFile,"%\r\n");
}

shortestLenAdjust(myNode,wArr,n,u);/*shortest path length adjust*/
}
fprintf(outputFile,"\r\nThe shortest path's lenth in this Graph is:%d\r\n",myNode[endNodeId].l_u);

/******************End of Core program**********/
endTime=(double)clock()/(double)CLOCKS_PER_SEC;
tweenTime=endTime-startTime;/*Get the time collapsed*/
/*Time collapsed output*/
printf("the collapsed time in this algorithm implement is:%f\n",tweenTime);
fprintf(outputFile,"the collapsed time in this algorithm implement is:%f\r\n",tweenTime);
printf("\n*******end of test program******\n");
#endif
/*Memory Free out*/
for(i=0;i<row;i++)
free(wArr[i]);
free(wArr);

printf("program end successfully,\n you have to preess any key to clean the buffer area to output,otherwise,you wiil not get the total answer.\n");
getchar();/*Screen Delay Control*/
return;
}

//测试结果:
//Inputdata
6,6,
0,5,
0,4,2,-1,-1,-1;
4,0,1,5,-1,-1;
2,1,0,8,10,-1;
-1,5,8,0,2,6;
-1,-1,10,2,0,3;
-1,-1,-1,6,3,0;
//OutpoutData
The shortest path's node sequence using dijkstra algorithm in this Graph is:
0,2,1,3,4,5,
The shortest path's lenth in this Graph is:13
the collapsed time in this algorithm implement is:0.000000

function [path, totalCost, farthestPreviousHop, farthestNextHop] = dijkstra(n, netCostMatrix, s, d, farthestPreviousHop, farthestNextHop)
% path: the list of nodes in the path from source to destination;
% totalCost: the total cost of the path;
% farthestNode: the farthest node to reach for each node after performing
% the routing;
% n: the number of nodes in the network;
% s: source node index;
% d: destination node index;

% clear;
% noOfNodes = 50;
% rand('state', 0);
% figure(1);
% clf;
% hold on;
% L = 1000;
% R = 200; % maximum range;
% netXloc = rand(1,noOfNodes)*L;
% netYloc = rand(1,noOfNodes)*L;
% for i = 1:noOfNodes
% plot(netXloc(i), netYloc(i), '.');
% text(netXloc(i), netYloc(i), num2str(i));
% for j = 1:noOfNodes
% distance = sqrt((netXloc(i) - netXloc(j))^2 + (netYloc(i) - netYloc(j))^2);
% if distance <= R
% matrix(i, j) = 1; % there is a link;
% line([netXloc(i) netXloc(j)], [netYloc(i) netYloc(j)], 'LineStyle', ':');
% else
% matrix(i, j) = inf;
% end;
% end;
% end;
%
%
% activeNodes = [];
% for i = 1:noOfNodes,
% % initialize the farthest node to be itself;
% farthestPreviousHop(i) = i; % used to compute the RTS/CTS range;
% farthestNextHop(i) = i;
% end;
%
% [path, totalCost, farthestPreviousHop, farthestNextHop] = dijkstra(noOfNodes, matrix, 1, 15, farthestPreviousHop, farthestNextHop);
% path
% totalCost
% if length(path) ~= 0
% for i = 1:(length(path)-1)
% line([netXloc(path(i)) netXloc(path(i+1))], [netYloc(path(i)) netYloc(path(i+1))], 'Color','r','LineWidth', 0.50, 'LineStyle', '-.');
% end;
% end;
% hold off;
% return;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% all the nodes are un-visited;
visited(1:n) = 0;

distance(1:n) = inf; % it stores the shortest distance between each node and the source node;
parent(1:n) = 0;

distance(s) = 0;
for i = 1:(n-1),
temp = [];
for h = 1:n,
if visited(h) == 0 % in the tree;
temp=[temp distance(h)];
else
temp=[temp inf];
end
end;
[t, u] = min(temp); % it starts from node with the shortest distance to the source;
visited(u) = 1; % mark it as visited;
for v = 1:n, % for each neighbors of node u;
if ( ( netCostMatrix(u, v) + distance(u)) < distance(v) )
distance(v) = distance(u) + netCostMatrix(u, v); % update the shortest distance when a shorter path is found;
parent(v) = u; % update its parent;
end;
end;
end;

path = [];
if parent(d) ~= 0 % if there is a path!
t = d;
path = [d];
while t ~= s
p = parent(t);
path = [p path];

if netCostMatrix(t, farthestPreviousHop(t)) < netCostMatrix(t, p)
farthestPreviousHop(t) = p;
end;
if netCostMatrix(p, farthestNextHop(p)) < netCostMatrix(p, t)
farthestNextHop(p) = t;
end;

t = p;
end;
end;

totalCost = distance(d);

return;

clc;clear;
M=1000;
a(1,2)=56; a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;
a(2,3)=21;a(2,4)=57; a(2,5)=78;a(2,6)=70;
a(3,4)=36;a(3,5)=68;a(3,6)=68;
a(4,5)=51; a(4,6)=61;a(5,6)=13;
[i,j]=find((a~=0)&(a~=M));
b=a(find((a~=0)&(a~=M)));
data=[i';j';b'];index=data(1:2,:);
loop=max(size(a))-1;
result=[];
while length(result)<loop
temp=min(data(3,:));
flag=find(data(3,:)==temp);
flag=flag(1);
v1=data(1,flag);v2=data(2,flag);
if index(1,flag)~=index(2,flag)
result=[result,data(:,flag)];
end
if v1>v2
index(find(index==v1))=v2;
else
index(find(index==v2))=v1;
end
data(:,flag)=[];
index(:,flag)=[];
end
result
在matlab中运行