using System;
using System.Collections.Generic;
namespace dijkstra {
class Program {
static void Main(string[] args) {
int SIZE = 6;
int[] d = new int[SIZE]; //
int[] refresh = new int[SIZE]; //3
List opened = new List(); // очередь обработки
int new_path, point, path, finish;
int[,] matrix = new int[,] {
{ 0, 7, 9, 0, 0, 14 },
{ 7, 0, 10, 15, 0, 0 },
{ 9, 10, 0, 11, 0, 2 },
{ 0, 15, 11, 0, 6, 0 },
{ 0, 0, 0, 6, 0, 9 },
{ 14, 0, 2, 0, 9, 0 }
};
/*
for (int i = 0; i < SIZE; i++) {
for(int j = i + 1; j < SIZE; j++) {
Console.Write("расстояние {0} - {1}: ", i + 1, j + 1);
temp = Convert.ToInt32(Console.ReadLine());
matrix[i, j] = temp;
matrix[j, i] = temp;
}
}
*/
// Вывод матрицы связей
Console.Write("\n \t");
for (int i = 0; i < SIZE; i++) Console.Write("{0}\t", i + 1);
Console.Write("\n\n");
for (int i = 0; i < SIZE; i++) {
Console.Write("{0}\t", i + 1);
for(int j = 0; j < SIZE; j++) Console.Write("{0}\t", matrix[i, j]);
Console.Write("\n");
}
Console.Write("\n");
// Инициализация
for (int i = 0; i < SIZE; i++) d[i] = -1; // путь неизвестен
d[0] = 0;
opened.Add(0);
while (opened.Count > 0) {
point = opened[0];
opened.Remove(point);
path = d[point];
for(int i = 0; i < SIZE; i++) {
if(matrix[point, i] > 0) { // если из point есть путь в i
new_path = path + matrix[point, i]; //новый путь из point в i
if (new_path < d[i] || d[i] == -1) { // если новый путь меньше уже имеющегоса или путь еще не известен
d[i] = new_path; // сохранаем новый путь
refresh[i] = point; // сохранаем, кто обновил точку i
if (opened.IndexOf(i) == -1) opened.Add(i); // если i нет в очереди, добавим его
}
}
}
}
Console.Write("кратчайшие расстояния: ");
// Вывод матрицы связей
for(int i = 0; i < SIZE; i++) Console.Write("{0} ", d[i]);
Console.Write("\n");
finish = 4;
int tmp = finish;
Console.Write("путь: ");
while (tmp != 0) {
Console.Write("{0} ", tmp + 1);
tmp = refresh[tmp];
}
Console.WriteLine("1, сумма: {0}", d[finish]);
Console.ReadKey();
}
}
}