Nathania21 Ответов: 1

Как создать представление матрицы смежности в Python


Мне дали образец досье. Каждая строка содержит: два узла и стоимость
Я хочу создать список, в котором у меня есть представление матрицы смежности, из которого я могу реализовать алгоритм кратчайшего пути Дейкстры.
Например, предположим, что мне дали этот пример графика:

0 3 .92
0 6 .97
1 2 .94
1 3 .91
1 4 .93
2 3 .95
2 4 .98
2 5 .92
3 5 .91
4 5 .94
4 6 .99
5 6 .92

Как бы я изменил содержимое файла на представление матрицы смежности?

Я бы жестко закодировал это, но мне нужен сценарий, в котором я не знаю содержимого файла, и я хочу иметь представление матрицы смежности файла, которое может содержать до 20 узлов.

Я надеюсь, что это имеет смысл.
Любая помощь будет очень признательна. Спасибо

Что я уже пробовал:

Мне просто нужна идея о том, как это сделать

Richard MacCutchan

Это математический вопрос. Как только вы поймете математику, то код Python должен быть довольно простым.

1 Ответов

Рейтинг:
2

CPallini

Я бы сделал это вот так:

  • Сканируйте файл, чтобы найти минимальные и максимальные индексы строк и столбцов. Для простоты предположим, что минимумы-это нули, а максимумы-это max_row и max_col.
  • Создайте двумерный список, имеющий (max_row + 1) строки и (max_col + 1) столбцы. Инициализируйте все элементы двумерного списка с помощью 0.
  • Сканируйте файл еще раз, присваивая соответствующее значение соответствующему элементу двумерного списка (например, 0 3 .92 => m[0][3] = .92.

Вот и все, ребята.


[обновление]
Исправлен неправильный индекс столбца, благодаря Патрис Ти.
[/обновление]


Patrice T

Вы уверены ?

0 3 .92 => m[0][2] = .92
  ^             ^

Richard MacCutchan

Вы слышали о польской нотации; это итальянская версия, которая гораздо более расслаблена. :)

CPallini

Действительно. :-D

Patrice T

Лично я предпочитаю обратную польскую нотацию (RPN)?
Потому что я научился пользоваться калькуляторами с папиным HP67. :)

CPallini

Действительно, это расслабленная итальянская нотация.
Спасибо, что указали на это.