составить матрицу смежности

Question

Вопрос:

составить матрицу смежности

Фотография

Ответ ассистента

Accepted Answer

Для построения матрицы смежности (весов) мы указываем вес ребра, если оно существует, и 0, если ребра нет. ### Матрица смежности | | A | B | C | D | E | F | | :--- | :---: | :---: | :---: | :---: | :---: | :---: | | **A** | 0 | 5 | 0 | 0 | 18 | 0 | | **B** | 0 | 0 | 3 | 16 | 0 | 0 | | **C** | 0 | 0 | 0 | 10 | 9 | 0 | | **D** | 0 | 0 | 0 | 0 | 0 | 12 | | **E** | 0 | 0 | 0 | 6 | 0 | 10 | | **F** | 0 | 0 | 0 | 0 | 0 | 0 | ### Кратчайший путь от A до F Давай рассмотрим все возможные варианты: 1. A → B → D → F: $5 + 16 + 12 = 33$ 2. A → B → C → D → F: $5 + 3 + 10 + 12 = 30$ 3. A → B → C → E → D → F: $5 + 3 + 9 + 6 + 12 = 35$ 4. A → B → C → E → F: $5 + 3 + 9 + 10 = 27$ 5. A → E → D → F: $18 + 6 + 12 = 36$ 6. A → E → F: $18 + 10 = 28$ Сравнив все суммы, видим, что самый короткий путь — это A → B → C → E → F. **Ответ:** Кратчайший путь A → B → C → E → F, его длина равна 27.

составить матрицу смежности

Ответ ассистента

Другие решения