using System;
using System.Collections.Generic;
using System.Text;
namespace ShortPath
{
/// <summary>
/// 计算加权图的最短路径
/// </summary>
class Program
{
/// <summary>
/// 邻接矩阵
/// </summary>
protected static int?[,] EdgeMetrix;
/// <summary>
/// 经过顶点的标示符
/// </summary>
protected static int[] Space;
/// <summary>
/// 起点到各点最短路径
/// </summary>
protected static int?[] ShortDistance;
/// <summary>
/// 最短路径线路
/// </summary>
protected static string[] Path;
/// <summary>
/// 顶点个数
/// </summary>
protected static readonly int NumVertices = 10 ;
/// <summary>
/// 起点
/// </summary>
protected static int StartIndex;
static void Main(string[] args)
{
Space = new int[NumVertices];
ShortDistance = new int?[NumVertices];
Path = new string[NumVertices];
FillEdgeMetrix();
Console.WriteLine("请输入起始点");
string StrIndex = Console.ReadLine();
if(Int32.TryParse(StrIndex,out StartIndex))
{
ComputeShortPath(StartIndex);
PrintShortPath();
Console.ReadLine();
}
}
/// <summary>
/// 填充邻接矩阵
/// </summary>
static void FillEdgeMetrix()
{
EdgeMetrix = new int?[NumVertices, NumVertices];
EdgeMetrix[0, 1] = 45;
EdgeMetrix[0, 2] = 35;
EdgeMetrix[0, 3] = 50;
EdgeMetrix[1, 8] = 70;
EdgeMetrix[1, 2] = 20;
EdgeMetrix[1, 5] = 90;
EdgeMetrix[2, 4] = 50;
EdgeMetrix[3, 4] = 50;
EdgeMetrix[5, 8] = 50;
EdgeMetrix[5, 6] = 20;
EdgeMetrix[5, 7] = 50;
EdgeMetrix[6, 0] = 40;
EdgeMetrix[6, 3] = 40;
EdgeMetrix[9, 8] = 35;
for (int i = 0; i < NumVertices;i++)
{
EdgeMetrix[i, i] = 0;
}
}
/// <summary>
/// 计算最短路径
/// </summary>
static void ComputeShortPath(int Index)
{
Space[Index] = 1;
int Predistance;
for (int i = 0; i < NumVertices; i++)
{
//非对角线的值
if (i != Index)
{
//当Index 到 I 可达时
if (EdgeMetrix[Index, i] != null)
{
if (ShortDistance[Index] != null)
{
Predistance = (int)ShortDistance[Index];
}
else
{
Predistance = 0;
}
//如果起点到达当前顶点的最短路径 + 当前顶点到指定定点路径 小于 指定顶点路径,或者第一次由于最短路径为null时 ，替换
if (Predistance + EdgeMetrix[Index, i] < ShortDistance[i] || ShortDistance[i] == null)
{
if (IsStartIndexCanArrive(Index))
{
ShortDistance[i] = Predistance + EdgeMetrix[Index, i];
//将路径记录下来
if (Index == StartIndex)
{
Path[i] = StartIndex.ToString() + "-->" + i.ToString();
}
else
{
Path[i] = Path[Index] + "-->" + i.ToString();
}
}
}
}
}
}
int NextIndex = FindMinIndex();
if (NextIndex != -1)
{
ComputeShortPath(NextIndex);
}
}
/// <summary>
/// 当前顶点是否为起点可达
/// </summary>
/// <param name="?"></param>
/// <returns></returns>
static bool IsStartIndexCanArrive(int Index)
{
bool IsArrive = false ;
if(Index == StartIndex )
{
IsArrive=true ;
}
else if (Path[Index] != null)
{
if (Path[Index].IndexOf(StartIndex.ToString()) != -1)
{
IsArrive = true;
}
}
return IsArrive ;
}
/// <summary>
/// 获取未标示位的最小值的Index
/// </summary>
/// <returns></returns>
static int FindMinIndex()
{
int Minvalue = -1;
int MinIndex = -1;
for (int i = 0; i < Space.Length; i++)
{
if (Space[i] != 1)
{
if (Minvalue == -1)
{
Minvalue = Space[i];
MinIndex = i;
}
else if (Minvalue < Space[i])
{
Minvalue = Space[i];
MinIndex = i;
}
}
}
return MinIndex;
}
/// <summary>
/// 打印起点到各点的最短路径
/// </summary>
static void PrintShortPath()
{
Console.WriteLine("起始点为 " + StartIndex.ToString()+"\n");
Console.WriteLine("目的地\t"+"最短路程\t" + "路线");
for (int i = 0; i < NumVertices; i++)
{
Console.Write(i.ToString()+"\t");
if (ShortDistance[i] != null && ShortDistance[i] != 0)
{
Console.Write(ShortDistance[i].ToString());
}
else
{
Console.Write("NoPath");
}
Console.WriteLine("\t\t"+Path[i]);
}
}
}
}
#define MAX_VERTEX_NUM 100 //最大顶点数
#define MAX_INT 10000 //无穷大
typedef int AdjType;
typedef struct{
int pi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径
int end;
}PathType;
typedef char VType; //设顶点为字符类型
typedef struct{
VType V[MAX_VERTEX_NUM]; //顶点存储空间
AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
}MGraph;//邻接矩阵表示的图
//Floyd算法
//求网G（用邻接矩阵表示）中任意两点间最短路径
//D[][]是最短路径长度矩阵，path[][]最短路径标志矩阵
void Floyd(MGraph * G,int path[][MAX_VERTEX_NUM],int D[][MAX_VERTEX_NUM],int n){
int i,j,k;
for(i=0;i<n;i++){//初始化
for(j=0;j<n;j++){
if(G->A[i][j]<MAX_INT){
path[i][j]=j;
}else{
path[i][j]=-1;
}
D[i][j]=G->A[i][j];
}
}
for(k=0;k<n;k++){//进行n次试探
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(D[i][j]>D[i][k]+D[k][j]){
D[i][j]=D[i][k]+D[k][j];//取小者
path[i][j]=path[i][k];//改Vi的后继
}
}
}
}
}
int main(){
int i,j,k,v=0,n=6;//v为起点，n为顶点个数
MGraph G;
int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点的最短路径向量
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点最短路径长度向量
//初始化
AdjType a[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={
{0,12,18,MAX_INT,17,MAX_INT},
{12,0,10,3,MAX_INT,5},
