c计算最短路径距离和路径节点序列.doc
文本预览下载声明
地理信息系统上机作业报告
XX XXXXXXXXXXXX XXXX级X班
作业要求：
给定任意邻接矩阵和起始点，计算出最短路径距离和路径节点序列。
算法思路描述：
得到带权的有向图和邻接矩阵
引入辅助向量Dist,每个分量Dist[i]表示从起始点到每个终点vi的最短路径长度。
假定起始点在有向图中的序号为i0，并设定该向量的初始值为：Dist[i]=Cost[i0,i]，vi∈V。令S为已经找到从起点出发的最短路径的终点的集合。
选择Vj，使得Dist[j]=Min{ Dist[i] | Vi∈V-S},vj就是当前求得的一条从vi0出发的最短路径的终点，令S=S∪{vj}.
修改从vi0出发到集合V-S中任意一个顶点vk的最短路径长度。如果Dist[j]+Dist[j,k]Dist[k]，则：Dist[k]=Dist[j]+Cost[j,k].
重复第2、3步操作共N-1次，由此求得从vi0出发的到图上各顶点的最短路径是依据路径长度递增的序列。
程序实例图：
源代码及运行结果：
using System;
using System.Collections.Generic;
using System.Text;
namespace ShortedPath
{
class Program
{
static int length = 6;
static string[] shortedPath = new string[length];
static int noPath = 2000;
static int MaxSize = 1000;
static int[,] G = { { noPath, 50, 10, noPath, 30, 100 }, { noPath, noPath, 5, noPath, noPath, noPath }, { noPath, noPath, noPath, 50, noPath, noPath }, { noPath, noPath, noPath, noPath, noPath, 10 }, { noPath, noPath, noPath, 20, noPath, 60 }, { noPath, noPath, noPath, noPath, noPath, noPath } };
/////////输入当前邻接矩阵
static string[] PathResult = new string[length];
static int[] path1 = new int[length];
static int[,] path2 = new int[length, length];
static int[] distance2 = new int[length];
static void Main(string[] args)
{
int dist1 = getShortedPath(G, 0, 5, path1);
Console.WriteLine(点0到点5路径:);
for (int i = 0; i path1.Length; i++)
Console.Write(path1[i].ToString() + );
Console.WriteLine(长度: + dist1);
int[] pathdist = getShortedPath(G, 0, path2);
Console.WriteLine(点0到任意点的路径:);
for (int j = 0; j pathdist.Length; j++)
{
Console.WriteLine(点0到 + j + 的路径:);
for (int i = 0; i length; i++)
Console.Write(path2[j, i].ToString() + );
Console.WriteLine(长度: + pathdist[j]);
}
Console.ReadKey()
显示全部