Dijkstra算法求最短路径.doc

Dijkstra算法求最短路径.docDijkstra 算法求最短路径（C#版）
行如下图的路径，（vo是中心）:
5
VI
2
¥3
2
经过该算法后转化为下图
using System;
using ns;
using ;
n amespace Greedy {
class Marx
{
private int[] distance;
private int row;
private ArrayList ways = new ArrayList();
public Marx(int n,params int[] d)
{
= n;
distance = new int[row * row]; for (int i = 0; i < row * row; i++) {
[i] = d[i];
}
for (int i = 0; i < ; i++) // 到各点的路有 row-1 条
{
ArrayList w = new ArrayList(); int j = 0;
(j); (w);
}
}
//
public void Find_way()
{
ArrayList S = new ArrayList(1); ArrayList Sr = new ArrayList(1); int []Indexof_distance=new int[];
for(int i=0; i < row; i++)
{
Indexof_distance[i]=i;
}
( Indexof_distance[0] ); for (int i = 0; i < ; i++)
{
( Indexof_distance[i] );
}
(0);
有 row 个点，则从中心
存放中心点到每个点的距离
int[] D = new int[]; //
//
以上已经初始化了， S和Sr（里边放的都是点的编
号）
int Count = - 1;
while (Count>0)
{
// 假定中心点的编号是 0 的贪吃法求路径
for (int i = 0; i < row; i++)
D[i] = [i];
int min_num = (int)Sr[0]; // 距中心点的最小距离点编号
foreach (int s in Sr)
{
if (D[s] < D[min_num]) min_num = s;
}
// 以上可以排序优化 (min_num);
(min_num);
// 把 最 新 包 含 进 来 的 点 也 加 到 路 径 中
((ArrayList)ways[min_num]).Add(min_num);
//
foreach (int element in Sr)
{
int position = element * (th