Как найти кратчайший путь, пройденный набором точек прохождения в C? - PullRequest
Новая
       71

Как найти кратчайший путь, пройденный набором точек прохождения в C?

0 голосов
/ 22 октября 2018

Итак, у меня есть «макет» карты, структурированный, как показано ниже: 

    a--(2)--b--(2)--c
    |       |       |
   (1)     (1)     (1)
    |       |       |
    d       e       f
    |       |       |
   (1)     (1)     (1)
    |       |       |
    g       h       i
    |       |       |
   (1)     (1)     (1)
    |       |       |
    j--(2)--k--(2)--l

буквы (a, b, c, d ... и т. Д.) Представляют точки расположения.Числа между двумя буквами представляют расстояние между этими двумя точками.Например, расстояние между точкой «a» и точкой «b» равно 2, а расстояние между точкой «a» и точкой «d» равно 1.

Я пытаюсь найти способ вычислениякратчайший путь возможен из заданной начальной точки, набор точек должен пройти, а затем вернуться к начальной точке.Так, например, учитывая, что начальной точкой является точка «a», и мне нужно идти в точки «b», «e» и «c», наиболее оптимальный путь, который я могу выбрать, будет a -> b -> c -> b -> e -> b -> a с общим расстояниемпроехал 10 ед.Другой путь, по которому я мог бы пойти, - это a -> b -> e -> b -> c -> b -> a, то есть такое же расстояние (10 единиц).

В моем коде я сохранил каждую точку вместе с соответствующими расстояниями по отношению к другим точкам в структуре,Например: 

struct stopPoints {
    int  weights[10];
    char connectingPoints[10];
    int startBool;
};

Я сохранил информацию о каждой точке в строку, показывая точки, к которым она подключена, а также ее вес: 

char str[12][100] = {
    "a = S, 2.b, 1.d",
    "b = 2.a, 1.e",
    "c = 2.b, 1.f",
    "d = 1.a, 1.g",
    "e = 1.h, 1.b",
    "f = 1.i, 1.c",
    "g = 1.j, 1.d",
    "h = 1.k, 1.e",
    "i = 1.l, 1.f",
    "j = 1.g, 2.k",
    "k = 2.j, 1.h, 2.l",
    "l = 2.k, 1.i"
};

Примечание: Iудалось разделить каждую точку и сохранить всю информацию в свои отдельные структуры.Также обратите внимание, что в точке «а» есть буква S.Это указывает на то, что это отправная точка (а также конечная точка).

Я исследовал некоторые алгоритмы поиска пути, и наилучшим вариантом, который, на мой взгляд, может быть применим в этой ситуации, является алгоритм Дейкстры.,Единственная проблема заключается в том, что у меня есть точки, которые вообще не связаны, такие как точки "d" и "e", и тот факт, что мне также нужно перейти к определенным точкам (должны пройти точки), поэтому реализация этого будет несколькосложно.Мне нужен только кратчайший путь, начинающийся с начальной точки, идущий к обязательным точкам прохождения и возвращающийся обратно к начальной точке.

Как мне начать это?Любой совет приветствуется.

...