using System using System Collections Generic namespace graph39 class

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
using System;
using System.Collections.Generic;
namespace graph39
{
class MainClass
{
public static int Dijkstra(int n, int[,] graph, int start, int end, out List<int> path)
{
int[] d = new int[n];
bool[] U = new bool[n];
List<List<int>> p = new List<List<int>> ();
for (int i = 0; i < n; i++) {
d [i] = int.MaxValue;
U [i] = false;
p.Add (new List<int> ());
}
d [start] = 0;
while (true) {
int v = -1;
int min = int.MaxValue;
for (int i = 0; i < n; i++)
if ((d[i] < min) && !U[i]) {
min = d [i];
v = i;
}
if (v == -1)
break;
U [v] = true;
for (int u = 0; u < n; u++) {
if ((graph [v, u] > 0) && !U [u])
if (d [u] > d [v] + graph [v, u]) {
d [u] = d [v] + graph [v, u];
p [u] = new List<int> (p[v]);
p [u].Add (u);
}
}
}
path = p [end];
return d [end];
}
public static void Main (string[] args)
{
Console.WriteLine ("Введите n: ");
int n = int.Parse(Console.ReadLine());
int[,] graph = new int[n,n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
Console.Write("Введите расстояние между {0} и {1}: ", i + 1, j + 1);
graph [i, j] = int.Parse (Console.ReadLine ());
}
Console.WriteLine ("Введите первую вершину: ");
int start = int.Parse(Console.ReadLine()) - 1;
Console.WriteLine ("Введите вторую вершину: ");
int end = int.Parse(Console.ReadLine()) - 1;
List<int> path;
int length1 = Dijkstra (n, graph, start, end, out path);
if (length1 == -1) {
Console.WriteLine ("Невозможно найти путь между этими двумя ячейками");
return;
}
for (int i = 0; i < path.Count - 1; i++) {
graph [path [i], path [i + 1]] = 0;
}
int length2 = Dijkstra (n, graph, start, end, out path);
if (length2 == -1) {
Console.WriteLine ("Между этими двумя ячейками не существует путей, не совпадающих ни по одному ребру");
return;
}
Console.WriteLine ("Разница между двумя путями равна {0}", length2 - length1);
}
}
}