Кратчайшие пути между всеми парами вершин (Реализация на Java)

Java   23 декабря 2012  Автор статьи:  

В данной статье мы рассмотрим нахождение кратчайших путей в ориентированном графе с помощью перемножения матриц. Если вам требуется решить данную задачу не этим способом, то воспользуйтесь алгоритмом Флойда. Перемножение матриц решает задачу о нахождения кратчайшего пути между всеми парами вершин за O(N^4). Идея метода состоит в том, чтобы на каждом шаге k находить наикратчайший путь между вершиной i и j длиной меньше или равной k. Для этого нам необходима матрица расстояний изначального графа, она как будто будет перемножаться с матрицей, которую мы будем получать на k-ом шаге. Для перехода с шага k на шаг k+1 будет использоваться функция ExtendShortestPaths. Нам достаточно вызвать ее n раз и мы получим результат:

import java.util.Scanner;

public class Solution {
static int infinity = 100000000;
static int[][] ExtendShortestPaths(int[][] l, int[][] w)
{
int n = l.length;
int[][] a = new int[n][];
for(int i = 0; i < n; i++) { a[i] = new int[n]; } for(int i = 0;i < n; i ++) { for(int j = 0; j < n;j++) { a[i][j] = infinity; for(int k =0; k < n; k++) { a[i][j] = Math.min(a[i][j],l[i][k] + w[k][j]); } } } return a; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] w = new int[n][]; int l[][] = new int[n][]; for(int i = 0; i < n; i ++) { w[i] = new int[n]; l[i] = new int[n]; for(int j = 0; j < n; j++) { w[i][j] = in.nextInt(); if(w[i][j]==0) { w[i][j] = infinity; } if(i==j) { w[i][j]=0; } l[i][j] = w[i][j]; } } for(int i = 0; i < n; i++) { l = ExtendShortestPaths(l,w); } for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { System.out.print(l[i][j]+" "); } System.out.println(); } } }

Можно оптимизировать данный код, и написать ExtendShortestPaths за O(n^2*logn). Для этого достаточно понимать как писать перемножение матриц за это время.

Научиться программировать

  • на Delphi

  • на Java

  • на C++