Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

This is a Digital Library

With over 100,000 free electronic resource in Persian, Arabic and English

Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] - نسخه متنی

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

| نمايش فراداده ، افزودن یک نقد و بررسی
افزودن به کتابخانه شخصی
ارسال به دوستان
جستجو در متن کتاب
بیشتر
تنظیمات قلم

فونت

اندازه قلم

+ - پیش فرض

حالت نمایش

روز نیمروز شب
جستجو در لغت نامه
بیشتر
لیست موضوعات
توضیحات
افزودن یادداشت جدید










Chapter outline



Section 25.1 presents a dynamic-programming algorithm based on matrix multiplication to solve the all-pairs shortest-paths problem. Using the technique of "repeated squaring," this algorithm can be made to run in Θ(V3 lg V) time. Another dynamic-programming algorithm, the Floyd-Warshall algorithm, is given in Section 25.2. The Floyd-Warshall algorithm runs in time Θ(V3). Section 25.2 also covers the problem of finding the transitive closure of a directed graph, which is related to the all-pairs shortest-paths problem. Finally, Section 25.3 presents Johnson's algorithm. Unlike the other algorithms in this chapter, Johnson's algorithm uses the adjacency-list representation of a graph. It solves the all-pairs shortestpaths problem in O(V2 lg V + V E) time, which makes it a good algorithm for large, sparse graphs.

Before proceeding, we need to establish some conventions for adjacency-matrix representations. First, we shall generally assume that the input graph G = (V, E) has n vertices, so that n = |V|. Second, we shall use the convention of denoting matrices by uppercase letters, such as W , L, or D, and their individual elements by subscripted lowercase letters, such as Wij, lij, or dij. Some matrices will have parenthesized superscripts, as in or , to indicate iterates. Finally, for a given n × n matrix A, we shall assume that the value of n is stored in the attribute rows[A].



/ 292